JPH0743698B2 - Parallel data processor - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial field of application] The present invention provides a plurality of sets of basic calculation elements each including a calculation means and a memory means, and sets required data for the plurality of basic calculation elements. The present invention relates to a parallel data processing device for performing processing in parallel.

[Prior Art] Conventionally, a parallel data processing apparatus of this type has been used, for example, in the field of image processing to perform density conversion of an image composed of nxm pixels (n, m?

FIG. 3 is a block diagram showing the configuration of a conventional parallel data processing device used for density conversion of an image composed of 4 × 4 pixels as an example. Correspondingly, 16 sets of basic operation elements (10) each including an operation unit (1) and a memory unit (2) are arranged in a matrix, and a control unit (common to each basic operation element (10) ( 11)
It is configured such that arithmetic commands and data are input from.

In this way, the basic operation elements 10 arranged in a two-dimensional matrix form are called SIMD type.

In this configuration, an image (12) in which the density of each pixel is as shown in FIG. 4 (a) is set as shown in FIG. 4 (b) with conversion values corresponding to eight levels of density values. In the case of performing the density conversion by the conversion table (13), the density value of each pixel of the image (12) is first transferred to the basic operation element (10) of the set corresponding to each pixel, and the memory unit (2) Stored in. Next, the density value of the conversion table (13) and the converted value thereof are simultaneously transferred to each basic operation element (10) for each density step. Then, each basic operation element (1
In 0), when the density value of the conversion table having the same value as the density value stored in its own memory unit (2) is sent, the conversion value paired with this density value is taken in, and this is stored. It is stored as a density conversion value. This conversion process ends when the transfer of the eight-step density values and conversion values of the conversion table (13) is completed.

For example, if a pixel of a large image is configured by each of the basic operation elements 10 described above, all pixels can be simultaneously processed in parallel by the same instruction from the control unit 11. This is a global processing device in terms of classification of image processing processors. Applied to.

[Problems to be Solved by the Invention] However, when the above processing method is adopted, even when the density conversion is performed according to the conversion table (13) having the same content, each time a new image (12) is given, Since it is necessary to transfer the contents of the conversion table (13) sequentially in the order of density steps, there is a problem that it takes a long time to complete the conversion process even if the respective basic arithmetic elements (10) operate in parallel. It was

The present invention has been made to solve the above problems, and an object of the present invention is to provide a parallel data processing device that can perform data conversion using a conversion table at high speed.

[Means for Solving Problems] In the present invention, all the conversion values of the conversion table are stored in advance in the memory means of each basic operation element, and each basic operation element has a function of referring to the table. It is a thing.

[Operation] Each basic operation element performs a conversion process by individually referring to a conversion table stored in advance in the memory means in the data conversion process. Therefore, the conversion table needs to be transferred only once from the control means, and the speed can be increased by the number of times the transfer table is omitted.

[Examples] Hereinafter, the present invention will be described in detail based on illustrated examples.

FIG. 1 is a block diagram showing an embodiment of a set of basic arithmetic elements in a parallel data processing device to which the present invention is applied, with respect to a conventional arithmetic unit (1) and memory unit (2)
A shift register (3), an adder (4), and multiplexers (5) to (7) are added.

The shift register (3) is capable of parallel input and serial input, and outputs are parallel. The adder (4) adds "1" to the output of the shift register (3) and sequentially updates the output of the shift register (3). The multiplexer (5) switches the value input to the parallel input terminal of the shift register (3) to the output of the adder (4) or "0". The multiplexer (6) switches the path of the input data to the memory section (2) to the output side of the arithmetic section (1) or the external input data side. Further, the multiplexer (7) switches the path of address data to the memory section (2) to the output side of the shift register (3) or the external address input data side.

Data transfer between the arithmetic unit (1) and the memory unit (2) and between the arithmetic unit (1) and the shift register (3) is performed in 1-bit units. Therefore, when the memory capacity of the memory unit (2) is set to 2 n bits, the configuration is “1 bit × 2 n words”. On the other hand, the shift register (3) has an n-bit width.

The operation of the parallel data processing device in which each basic operation element is configured as described above will be described in detail below. However, each basic operation element processes one data, and this data is already stored in the memory unit (2).

(1). Regarding the operation of storing the conversion table in the memory section in each basic operation element.

In the case of this processing, first, the multiplexer (5) is switched to the side that selects the value of "0", and the value of "0" output from the multiplexer (5) is stored in the shift register (3) by this selection. By inputting in parallel, the shift register (3) is cleared. After that, the output of the shift register (3) is input as address data of the memory section (2) through the multiplexer (7), and is also input to the adder (4) to add "1" to the added value. To the parallel input of the shift register (3) multiplexer (5)
Input via.

After clearing the shift register (3), the operation of inputting a value obtained by adding "1" to the output of the shift register (3) to the shift register (3) again is repeated, and thus the address of the memory unit (2) is Address data that changes from "0" to "1" is input to the input. In synchronization with such a change in the address data, the contents of the conversion table are transferred from the external control unit to the memory unit (2) via the multiplexer (6).
Entered in. As a result, the conversion table is stored in the memory unit (2) in each basic calculation element.

When the conversion table is generated by the arithmetic unit (1), the multiplexer (6) is switched to the data output side of the arithmetic unit (1).

(2). About data conversion processing operation in each basic operation element.

The data to be converted is stored at the same address in the memory unit (2) in each basic operation element. Therefore, first, address data indicating the storage address of this data is first supplied from the outside and supplied to the memory section (2) through the multiplexer (7). As a result, the value to be converted is output bit by bit from the data output of the memory unit (2). On the other hand, the arithmetic unit (1) does not perform any processing, and the data to be converted is stored in the shift register (3) by the serial shift operation. After that, the multiplexer (7) is set to the selected state on the shift register (3) side,
The converted value is read from the memory unit (2). The converted value is
The data output from the memory unit (2) is sent to the arithmetic unit (1) and, if necessary, is sent to the outside.

By the way, the conversion value output from the memory unit (2) has a 1-bit configuration, but usually the conversion data is often 2 bits or more both before and after conversion. Therefore, do the following. It is assumed that the number of items in the conversion table is p, the number of bits required to express the converted value is q, and the value before conversion is a value from "0" to "p-1". , The value before conversion is represented by Log ₂ p bits. On the other hand, since the memory configuration of each basic operation element has 1 bit as 1 word, q words are required to store the converted value. That is, it is sufficient that there exist Log ₂ q bits as an address. Therefore, if (Log ₂ p + Log ₂ q) bits are prepared for the address of the memory unit (2), the upper Log ₂ p represents the value before conversion, and the lower Log ₂ q bits are set in order from “0” ( Log ₂ q-1) and increase this L
The converted value can be stored in the og ₂ q bits.

A specific example will be described with reference to FIG. The conversion table (8) stores values “0” to “15” (4-bit representation) before conversion. That is, when expressed by p and q, p = 16 and q = 4. Therefore, one address required for the memory section (2) is Log ₂ 16 = 4 bits for the upper and lower address for the lower
Log ₂ 4 = 2 bits, 6 bits in total. The upper 4 bits represent the value before conversion in the conversion table (8), and the lower 2
The converted value is stored in the 4 words that change from "00" to "11" in bits. For example, in the conversion table (8), the column of "7" before conversion and "13" after conversion is
The structure in the memory is as shown by the symbol (9) in FIG. 2 (b). In other words, this "7", the binary number "0111"
The value after the conversion to the area where the lower 2 bits change from “00” to “11” in the address area with the upper 4 bits as “13” (2
"1101") is sequentially stored in the base number. Then, the conversion value of "8" before conversion is stored from the next address "100000".

In FIG. 1, in order to read such a value, the value before conversion is stored in the shift register (3), and then "0" is placed in the lower order by the number of bits necessary for expressing the value after conversion. It is sufficient to read out from the memory unit (2) on the basis of the value thus generated. Further, for continuous reading, an adder (4) for adding the value of the shift register (3) by "1" may be used.

If the number of data to be processed exceeds the number of basic calculation elements, the number of basic calculation elements will be insufficient. In this case, each basic calculation element should be assigned a plurality of data processing, or The data to be processed may be divided in units of the number of basic operation elements, and processed for each divided unit.

By the way, in the above embodiment, the case where one conversion table is stored for each basic operation element has been described. However, if two conversion tables are held, the speed of multiplication and division can be increased. .

That is, in one of the two memories in each basic arithmetic element, one has the logarithmic value of the value before conversion and the other has the same exponent value of the base. Then, if it is desired to obtain the product of A and B, both A and B are referred to the above logarithmic conversion table to obtain LogA and LogB. After that, the two values are added, and the added value is converted by the exponential conversion table to obtain the product AB. For division, the above addition need only be subtraction.

That is, multiplication and division are completed only by three table references and addition or subtraction operations.

[Effects of the Invention] As described above, the present invention has the arithmetic means and the memory means, which are arranged in a two-dimensional lattice form and operate simultaneously by the same instruction given from one control unit. To the internal memory address register and the function to increase the value of that register by "1", give the same data conversion table to all basic operation elements, and set the internal data for each basic operation element. Is independently converted according to this data conversion table.
The effect that the data conversion using the data conversion table can be performed at high speed is obtained.

Further, the present invention requires (1) one control unit, so that only one program is required, (2) synchronization can be performed more easily than the conventional one, and (3) implementation becomes compact. (4) It is effective when a large number of pixels can be processed at one time.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of basic arithmetic elements in a parallel data processing device to which the present invention is applied, FIG. 2 is a diagram showing an example of a conversion table and a method of storing conversion values, and FIG. FIG. 4 is a block diagram of a conventional parallel data processing device, and FIG. 4 is an explanatory diagram for explaining the operation in FIG. (1) ... arithmetic unit, (2) ... memory unit, (3) ... shift register, (4) ... adder, (5) to (7) ... multiplexer, (8), (13) ... conversion table, ( 10) ... Basic operation elements, (11) ... Control unit.

Claims (1)

[Claims] 1. A large number of sets of basic arithmetic elements having an arithmetic unit (1), a memory unit (2), a shift register (3), an adder (4) and a multiplexer (7), and one Each of the above-mentioned basic operation elements is arranged on a two-dimensional lattice, and adjacent basic operation elements are connected to each other, and all the basic operation elements are the same by an instruction given from the one control section. A parallel data processing device for executing an instruction, comprising: a data conversion table for converting each of the arithmetic units into data unique to each basic arithmetic element stored at the same address of each of the memory units (2). When storing in the memory unit (2), the shift register (3)
The value obtained by sequentially increasing the content of the above from the initial state by "1" by the adder (4) is sequentially supplied to the memory unit (2) as an address of the memory unit (2) through the multiplexer (7), and data is supplied. When performing the conversion, the address in which the unique data is supplied, which is supplied from the control unit, is supplied to the memory unit (2) as the address of the memory unit (2) through the multiplexer (7) and read out. A value obtained by setting the shift register (7) to a value obtained by shifting the generated data according to the number of bits of the data conversion table and sequentially increasing the content of the shift register by "1" by the adder (4). Is sequentially supplied as an address of the memory unit (2) through the multiplexer (7) to obtain converted data. The basic arithmetic element of Te to give the same data conversion table, independently its internal data per each elementary operation element, the parallel data processing apparatus characterized by converting in accordance with the data conversion table.