FR2692382A1 - Parallel processor for processing multiple data by a series of repetitive instructions. - Google Patents

Abstract

A parallel processor comprising: an assembly (21) of alpha series of K elemental arithmetic units (UCEi,j), wherein each of the elemental arithmetic units (UCEi,j) has M data input lines (Lce) and N data output lines (Lcs), and each of said lines (Lce, Lcs) is connected to one of the input/output lines (Lces) of the assembly (21); a bulk memory (22) having O input/output lines (Lmes) for writing in and reading out words of O bits, said assembly (21) transferring data to and from said bulk memory; a transposing structure performing the "direct" conversion of a set of Q data items having P bits into P words having Q bits, said transposing structure further performing the "reciprocal" conversion of P' words having Q' bits into Q' data items having P' bits; and a set of ports (24) for transferring data to and from the assembly (21), the memory (22) and the transposing structure (23). Said processor may be used to perform repetitive processing, particularly image processing.

Description

The present invention relates to a parallel processor for

  fast processing of a large number of data according to an identical algorithm for each of the data Such a processor is in particular intended for image processing,

pixel by pixel, and real time.

  various types of parallel architecture processors are known in the state of the art, in particular processors operating according to the "simple instruction flow, multiple data streams" mode. For the processors of the state of the art, a single control unit manages the operation of a plurality of calculation units, and

  several data are processed simultaneously.

  The association of a large number of interconnected computing units, each integrating RAMs for storing data and processing information, as well as the result of

  treatments, forms a matrix network.

  The parallelism of the type "simple instruction flow, multiple data streams" is particularly suitable for low level processing, that is to say for point operations or on a neighborhood independent of the position of the pixel in

the image.

  US Pat. No. 4,144,566 describes in particular a parallel processor comprising a large number of elementary processors connected in parallel on an address bus and a control bus, and each comprising a memory and control and calculation means for operating calculations on the bits addressed in the memory and on bits coming either from the internal memory or external peripheral members The mass memory and said control and calculation means are interconnected to a fast memory of low capacity, the means control system comprising a single storage scale for serial operation of calculations on

2 2692382

  the bits extracted from the memory and / or from said device. By "control means" is meant in particular structures for routing information from one or more sources to one or more destinations, including multiplexers. In order to improve the power and the speed of calculation, US Pat. No. 4,215,401 describes a massive parallel processor comprising a plurality of elementary calculation units UCE, each of the elementary calculation units being connected to neighboring elementary calculation units for form a matrix of interconnected elementary computing units of dimension N x M The elementary calculation units are

  further connected to a central controller.

  Each of the elementary calculation units comprises a random access memory, an accumulator with an input bit, an accumulator with an output bit and a NAND gate. The use of NAND gates as the processing unit, and the organization of the memories imply a relative complexity of the training sequences and

  a limitation of the processing speed.

  European Patent 0 122 048 discloses a parallel data processing computer, comprising a plurality of processing cells (P) and a controller for generating control signals in response to program instructions, each cell comprising an element arithmetic processor having three input terminals (D1, D2, C) and a plurality of output terminals (PLUS, RETENTION; +, CY, BW) Each cell further comprises a plurality of controllable memories for providing data input signals to the input terminals of the processing element in response to control signals from the controller The memories are connected to the controller and the arithmetic processing element

3 2692382

  such that both arithmetic operations and logical operations, including logical operations involving a plurality of data input signals, can be performed by the arithmetic processing element in response to the selective application a logic level of a binary ONE or binary ZERO from one of the memories to one of the input terminals of the processing element. The purpose of the present invention is to optimize the processor in order to balance the resources devoted to the management of data formatting and the supply of the elementary computing units to data on the one hand, and the resources devoted to at the execution of logical processing and / or

arithmetic on the other hand.

  For this purpose, the invention relates more particularly to a parallel processor constituted, in addition to a control part generating all the commands necessary for the operation of the part assigned to the calculation and data management, by: a set of UCE of a series of elementary calculating Kunits UC Eij, i denoting an integer between 1 and acet j denoting an integer between 1 and K, said set comprising L input-output lines, each of the elementary calculation units UC Ei, j having M lines Lce for data input and N lines Lcs for data output, each of these lines Lce, Lcs being connected to one of the input-output lines Lces of the set; a large-capacity mass memory having O lines of input-output Lmes for writing and reading O-bit words, the set exchanging data with said mass memory; a transposition structure performing the so-called "direct" transformation of a set of Q data of P bits into a set of P words of Q bits,

4 2692382

  a word being constituted by the association of the Q bits of equivalent weight of the given Q's, the said transposition structure ensuring, moreover, the so-called "reciprocal" transformation of P 'words of Q' bits into Q 'data of P' bits Such a structure communicates with the input-output ports by means of the input of "data" having respectively P and P 'bits, and with the mass memory by "words" having respectively Q and Q' bits. The lines allowing these exchanges can be one-way or two-way, and distinct or common for "data" and "word" transfers; a set of ports allowing the exchange of data between the transposition structure or the mass memory on the one hand and the outside on the other hand The different ports do not necessarily have the same number of lines, and can be individually mono -directional or bidirectional; the set of UCE exchanging data with the memory, the memory exchanging data with the transposition structure and with the set of ports and the transposition structure exchanging data.

data with the set of ports.

  In the present description, a "Data"

  groups all the bits of the same information.

  A "Word" includes all the bits of

  same weight of a dataset.

  The translation of data into words is referred to as "direct transposition" while the translation of "words" into "data" is designated by

"reciprocal transposition".

  In the processor according to the invention, each of the elementary calculation units UC Ej, j carries out an identical processing on the data coming from the mass memory, according to instructions provided identically by the central controller to each elementary calculation unit UC Ei, j This mode of

2692382

  realization allows to limit the flow of data and thus speed up the processing speed of a number

important data.

  The number x K of elementary calculation units is typically between a few tens and several thousand, and depends essentially on the technological progress in

circuit integration.

  The number L of input-output lines is equal to the number of calculation units, to a sub-multiple

or a multiple of that number.

  The number M of entries of each of the elementary calculation units is typically between 1

and 32.

  The number N of outputs of each of the elementary calculation units is typically comprised

between 1 and 32.

  the length O of input-output lines LMS of the mass memory of large capacity is equal to L or to a sub-multiple of L. P and P 'are equal to the number of lines of the external ports to which they are connected Q and Q 'are equal to the length O of input-output lines Lmes of the mass memory or to

sub-multiple of 0.

  The transfers between the set of elementary calculation units and the high-capacity memory depend on the values of O and L: * if O = L, all the information present at the output of one of the elements is transferred in one cycle at the input of the other element * if O <L, the information present at the output of the set of elementary calculation units is transmitted in whole or in part in one or more cycles, this being connected for each cycle O L lines of the set of computational units elementary O rows of the memory of large capacity The information present at the output of the

6 2692382

  large capacity memory are transmitted in a cycle at O of the L rows of the set of elementary calculation units the elementary calculation units not

  solicited are blocked in writing.

  The transfers between the high capacity memory and the transposition structure depend on the values of O, Q and Q '* if Q = O The set of information present at the output of the transposition structure is transferred in a cycle to the input of the large capacity memory * If Q <O The information present at the output of the transposition structure is transmitted in one cycle to Q of the O lines of the high-capacity memory part of the large-capacity memory

  unsolicited is blocked in writing.

  * if Q '= L The set of information present at the output of the high-capacity memory is transferred in a cycle to the input of the transposition structure * if Q' <O the information present at the output of the high-capacity memory are transmitted in whole or in part in one or more cycles by connecting, for each cycle, Q O lines of the high capacity memory to the Q lines

transposition structure.

  The transfers of the large-capacity memory to the set of ports as well as the transfers between the set of ports and the high-capacity memory depend on the values of R denoting the number of lines of the ports requested by the transfer which is less than O. For transfers from high capacity memory to an output configured port, the information present at the output of the high capacity memory is transmitted in whole or in part in one or more cycles, by connecting

7 2692382

  R O rows of high-capacity memory to R

  lines of the port solicited at the output, for each cycle.

  For transfers from a port configured as an input to the high-capacity memory, the information on the port configured as input is transmitted in one cycle to R of the O lines of the high-capacity memory.

  solicited is blocked in writing.

  The transfers between a port and the transposition structure depend on the values of P, P 'and R. The information present at the "data" output of the transposition structure is transmitted in one cycle to the port configured at the output (R =

P).

  The information present on a port configured as input is transmitted in one cycle to the "data" input of the transposition structure (R = P). According to a simplified embodiment, each of the K elementary calculation units UC Ej of a series i of elementary calculation units UC Ei, j accesses the memory elements Mj-r to Mj + r and writes to the memory elements Mj-s to Mj + s without exchanging data with a unitary calculation unit UC Ej T or jEj 'Advantageously, each of the K elementary calculation units UC Ei, j accesses the memory elements Mi-t, jr to Mi + t , j + r and written in the memory elements Mi-u, js to Mi + uj + s without exchanging data with a unitary calculation unit UC Eji, jr oIEil and jEj '. The present invention will be better understood at

  reading the following description, making

  1 schematically represents the environment of a processor according to the invention; FIG. 2 represents the general structure of the processor according to the invention;

8 2692382

  FIG. 3 schematically represents the architecture of a memory element of the transposition structure, according to a first embodiment of FIG.

production; -

  FIG. 4 represents the network of memories and the links with the various BUSs; FIG. 5 represents the block diagram of a cell of the memory network; FIG. 6 schematically represents the architecture of a second embodiment of a memory element of the transposition structure; FIG. 7 represents the network of memories and the links with the various BUSs; FIG. 8 represents the block diagram of a cell of the memory network; Figure 9 schematically shows the architecture of a third embodiment of a memory element of the transposition structure; FIG. 10 represents the network of memories and the links with the various BUSs; Fig. 11 shows the block diagram of a cell of the memory array; Figure 12 shows the architecture

  a Basic Calculus Unit.

  FIG. 1 shows the overall architecture of an exemplary application of a processor according to the invention. The image processing chain

  essentially comprises three modules (1 to 3).

  The first module consists of an imaging workstation (1) capable of acquiring and reproducing images in real time, connected to

  a digital camera (5) and a monitor (6).

  This workstation is generally equipped with a video processor (7) provided with a local program memory (8), a data memory (9) for storing information from a camera, or for transfer to a monitor, and several operators wired for

  perform specific functions.

  The second module (3) can be composed of a single processor or a multiple Multiple instruction type given processor, whose elementary processor can be a processor

  classic, a vector processor, a transputer.

  This second module (3) ensures the medium and high level transformations such as the passage

  list image and the processing of these lists.

  The third module (4) is constituted by a processor according to the invention, comprising a calculation structure (101) intended for video real-time processing on the basis of lower algorithms.

  level in image processing (neighborhood calculations).

  This computing structure (101) receives commands from a central controller (102) generating the instructions necessary for the operation of the

computing structure (101).

  The entire architecture is connected on the one hand to a standard industrial bus (referenced "Multibus" in Figure 1) for commands, and secondly on a set of digital video BUS (referenced "BUS images" in FIG. 1) for data exchanges that allow pipeline type exchanges or, by a referral system,

more complex communications.

  Figure 2 shows the structure

  general processor according to the invention.

  In the example described, the processor comprises: a set of UCE (21) of 512 identical elementary calculation units This set forms a uni-dimensional network in which each elementary processor has an output line and 7 d-lines Each of the lines of index i among the L = 512 input-output lines of the set of ECUs (21) is connected to the output of the elementary processor of index i and to the input of the 7 processors elementary

of index i-3 to i + 3.

  a mass memory (22) having 512 data input-output lines and which allows

the writing of 512-bit words.

  a transposition structure (23) composed of two identical and independent transposition memories 32 * 512 each having an address allowing reading or writing in a "given" format (32 bits) and reading and writing in the format "word" (512 bits) Each of the transposition memories makes it possible at any time to perform either a transposition of data-words or a transposition.

data words.

  a set of ports (24) composed in the example described of two bi-directional 32-bit ports. The processor according to the invention communicates with its external environment by 32-bit data (Q = Q '= 32) On the other hand, the communication between the set of calculation units (21) and the mass memory (22) as well as the communication between the mass memory and the transposition structure is carried out with data of 512 bits

(K = L = O = P = P '= 512).

  The following description concerns more

  particularly different embodiments of

the transposition structure.

  The transposition of 32-bit "words" into "data" of 512 bits is provided by one or more so-called transposition memories or "orthogonal memories". Such elements make it possible to perform either direct transformations (writing of "data", reading of "words"), ie the reciprocal transformations (writing of "words", reading of "data"),

either the two transformations.

  2692382 The writing or reading of information in a format can be done either by shift or by addressing. Three types of transposition elements can be distinguished: a first type with orthogonal double offset o the shift in one direction corresponds to the access in one format while the offset in an orthogonal direction corresponds to the access in the other format; a second type with double crossed addressing, an addressing corresponding to the access in one format and the other addressing corresponding to the addressing in the other format; a third hybrid type allowing access to a shift format and access to the other

format by addressing.

  FIGS. 3 to 11 represent transposition memories having address and word accesses by addressing. In the case where the transposition structure (23) is composed of a read translation memory "words" and read write "data" such a memory makes it possible to carry out both the direct transformations that

  reciprocal, as illustrated in Figures 3 to 5.

  FIG. 3 schematically represents the architecture of the transposition structure, constituted by a read and write memory "data" and read write "words". FIG.

  memories and links with different BUS.

  Each cell (28 to 31) of which FIG. 5 represents the block diagram communicates with: write command lines "words" (32), read command lines "words" (33) "data" lines "Writing (34) lines of" data "in Reading (35) lines of" words "in Writing (36)

122692382

  lines of "words" in Reading (37) command lines Write "data" (38) command lines Read "data"

(40).

  Each elementary cell (28 to 31) comprises: an OR gate (41) whose inputs receive the "Write" command and Write command commands "words" via the lines (32) and (38), an OR gate whose inputs are connected to the lines of "words" for writing (36) and of "data" in Writing (34) a memory (45) a gate (43) controlled by the signal coming from the command lines of Reading "words" (33) and whose output is connected to the reading "word" lines (37) a gate (44) controlled by the signal from the "data" read command lines (40) and whose output is connected to the lines of

"Data" in Reading (35).

  In the case where the memory element of the transposition structure (23) does not provide the two transformations, it is possible to distinguish a first memory architecture which ensures the direct transformation of data into words (FIGS. 6 to 8) and a second memory architecture that ensures the reciprocal transformation of words into data (Figure 9

to 11).

  FIG. 6 represents the general architecture of the "Write" memory and the "Word" read. FIG.

  memories and links with different BUS.

  Each cell (50 to 53) of which FIG. 8 represents the block diagram communicates with:

13 2692382

  command lines for reading "words" (57) lines of "data" in writing (55) lines of "words" in reading (56) lines of writing command "data" (54) each elementary cell (50 to 53) comprises: a memory (58) receiving the signals the write command lines "data" (54) and lines of "data" in writing (55), a door (59) controlled by the signal from the command lines of Reading (57) and whose output is connected to the lines of "words" in

Reading (56).

  FIG. 9 represents the general architecture of the second memory, reading "data" and writing "words". FIG.

  memories and links with different BUS.

  Each cell (60 to 63) of which Fig. 11 represents the block diagram communicates with: write command lines "words" (67), read "data" lines (66) lines of "words" in Writing (64) "Data" read command lines (65) Each elementary cell (60 to 63) comprises: a memory (68) receiving the signals of the write command lines (67) and lines of " "Writing" (64), a gate (69) controlled by the signal from the read control lines (65) and whose output is connected to the data lines in

Reading (66).

  FIG. 12 represents the architecture of an elementary computing unit Each elementary computing unit is constituted by two RAM I RAMs (70) and RAM II (71), of the dual access memory type to enable reading and writing simultaneous to different addresses, each consisting of r words of one bit, and by two computing structures, the first computing structure (72) being an arithmetic and logical bit series unit and the second computing structure (73) being a unit arithmetic

parallel word.

  The elementary computing unit further comprises a set (74) of multiplexers and registers connecting the outputs and inputs of the elements. In the example described, there is a

  output line and 7 data input lines.

  The present invention is described in the foregoing with reference to an exemplary embodiment.

non-limiting.

2692382

Claims (6)

R E V E N D I C A T IO N S   A parallel processor comprising a plurality of identical elementary calculation units, memories for storing the data and at least one controller generating all the commands necessary for the operation of the part assigned to the calculation and the management of the data, characterized in what it comprises: a set of (21) of a series of K elementary calculation units UC Ei, j, i denoting an integer between 1 and a and j denoting an integer between 1 and K, said set comprising L input-output lines, each of the elementary calculation units UC Ei, j having M lines Lce for the data input and N lines LCS for the data output, each of these lines Lce, Lcs being connected to the one of the input-output lines Lces of the set (21); a mass memory (22) of large capacity having O lines of input-output Lmes for writing and reading O-bit words, the set (21) exchanging data with said mass memory (22) ; a transposition structure performing the so-called "direct" transformation of a set of Q data of P bits into a set of P words of Q bits, a word being constituted by the association of the Q bits of equivalent weight of the Q data, said transposition structure also ensuring the so-called "reciprocal" transformation of P 'words of Q' bits into Q 'data of P' bits Such a structure communicates with the input-output ports thanks to the input of "data" having respectively P and P 'bits, and with the mass memory by "words" having respectively Q and Q' bits The lines allowing these exchanges can be monodirectional or bidirectional, and distinct 16 2692382   or common for transfers of "data" and "words"; a set of ports (24) for the exchange of data between the set (21), the memory (22) and the transposition structure (23), the set (21) exchanging data with the memory (22) , the memory (22) exchanging data with the transposition structure (23) and with the set of ports (24) and the transposition structure (23) exchanging data with the set of ports (24).   Parallel processor according to Claim 1, characterized in that each of the K elementary calculation units UC Ej of a series i of elementary calculation units UC Ei j accesses the memory elements Mj-r at Mj + r and written in the memory elements Mj-s to Mj + s without exchanging data   with an elementary calculating unit UC Eji or jEj '.   3 parallel processor according to claim 1 characterized in that each of the K elementary calculation units UC Ei, j accesses the memory elements Mi-t, jr Mi + t, j + r and writes in the memory elements Mi-u , js to Mi + uj + s without exchanging data with a unitary calculation unit UC Ejt, j I o Ii 'and iJ'. 4 Parallel processor according to one   any of the preceding claims characterized   in that transposition structure (23) is constituted by at least one read and write memory   Writing "Data" and Reading Writing "Words". 5 Parallel processor according to one   any of claims 1 to 3 characterized in that   that transposition structure (23) is composed of two types of memories, one of the types corresponding to "Writing" and "Reading" writing memories, the other corresponding to "word" writing memories. and reading "data". 6 Parallel processor according to one   any of the preceding claims characterized   in that each elementary calculation unit is constituted by two RAMs (70, 71) of the dual access memory type to enable simultaneous reading and writing to different addresses, each composed of r words of one bit, and by two computing structures, the first computing structure (72) being an arithmetic and logical serial bit unit and the second computing structure (73) being a parallel word arithmetic unit and further comprising a set (74) multiplexers and registers connecting the outputs and inputs of the elements.