Data-driven information processing device and method to access multiple bank memories according to multiple addresses

An address calculation unit calculates a plurality of addresses corresponding to a plurality of data included in a data packet. A first bank memory access unit accesses a first bank memory according to a first address calculated by the address calculation unit. Simultaneously, a second bank memory access unit accesses a second bank memory according to a second address calculated by the address calculation unit. A packet reconstruction unit reconstructs the data packet according to the results of access by the first and second bank memory access units. Accordingly the processing rate of the data packet including a plurality of data is increased.

This nonprovisional application claims priority under 35 U.S.C. § 119(a) on Patent Application No. 2001-387194 filed in JAPAN on Dec. 20, 2001, which is herein incorporated by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a data-driven information processing device. In particular, the present invention relates to data-driven information processing device and method with an improved processing rate for a data packet including a plurality of data.

2. Description of the Background Art

In recent years, there has been a growing demand for improvement of the performance of a processor in various fields like the fields of multimedia processing and high-definition image processing, for example, which require fast processing of a large volume of data. With the current LSI (large-scale integrated circuit) manufacturing technique, however, there is a limit to the increase of the speed of devices. Attention is then focused on parallel processing that is now studied and developed seriously.

Attention is drawn to computer architectures applied to parallel processing, in particular, to data-driven architecture. According to the data-driven processing architecture, parallel processing is carried out following a rule “if all of the input data necessary for certain processing are ready and such resources as operation unit required for the processing are allocated, that processing is executed.”

The applicant of the present application discloses in Japanese Patent Laying-Open No. 9-114664 a data-driven information processing device processing a data packet including a plurality of data.FIG. 1shows a structure of a data packet processed by this conventional data-driven information processing device. The data packet includes a tag section101and a data section102. Tag section101includes destination information103indicating a node number in a program, instruction information104indicating any type of arithmetic operation to be performed on a plurality of data included in data section102, and effective data information105indicating which of the multiple data included in data section102is effective. Data section102includes data0(106) and data1(107).

FIG. 2is a block diagram schematically showing a configuration of a data-driven processor processing the data packet as shown inFIG. 1. The data-driven processor includes a junction unit201, a firing control unit202, a memory control unit203, an operation unit204, a program storage unit205and a branch unit206. A plurality of data-driven processors of this type are connected in parallel to constitute a data-driven information processing device.

Junction unit201conducts arbitration of input between a data packet supplied from an input control unit (not shown) and a data packet supplied from branch unit206to provide these data packets to firing control unit202by arranging the data packets in order so as not to cause conflict therebetween.

For each data slot in the supplied data packet, firing control unit202determines whether or not there is an address for data to be subjected to operation (address at which the data to be subjected to operation is stored) in a queuing memory (not shown). If the supplied data packet and for each slot the address of data to be subjected to operation are present in the queuing memory, firing control unit202generates a data packet as shown inFIG. 1from these data addresses and outputs the generated data packet to memory control unit203. If the supplied data packet and any of the addresses for the data to be subjected to operation (address at which the data to be subjected to operation is stored) are absent in the queuing memory, firing control unit202stores the data in the queuing memory to wait for data addresses.

If data0(106) and data1(107) indicate respective addresses in a table memory (not shown), memory control unit203accesses the table memory to obtain the data values to be subjected to operation and generate a data packet including the data values.

Operation unit204refers to instruction information104to perform such operation as multiplication and addition on the data included in the data packet generated by firing control unit202or memory control unit203and provides the result of the operation to program storage unit205.

Program storage unit205receives the result of the operation from operation unit204to generate a data packet having exchanged destination information103necessary for fetch of a next instruction and instruction information104and output the generated data packet to branch unit206.

Branch unit206refers to destination information103in the data packet supplied from program storage unit205and, if branch unit206determines that the data should be processed in its own data-driven processor, branch unit206outputs the data packet to junction unit201. If branch unit206determines that the data should not be processed in the own data-driven processor, branch unit206provides the data packet to another data-driven processor.

FIG. 3is a block diagram showing details of memory control unit203inFIG. 2. Memory control unit203includes a packet copy unit301, an address calculation unit302, a memory access unit303and a packet reconstruction unit304.

If the data included in the data packet indicate addresses in the table memory, packet copy unit301refers to effective data information105to determine if data0(106) and data1(107) are effective. If the two data in data section102are effective, packet copy unit301copies the data packet to generate a first packet for data0(106) and a second packet for data1(107).

Address calculation unit302refers to data0(106) included in the first packet to perform address calculation. Memory access unit303accesses the table memory according to the address calculated by address calculation unit302to obtain data corresponding to the first packet.

Similarly, address calculation unit302refers to data1(107) included in the second packet to perform address calculation. Memory access unit303accesses the table memory according to the address calculated by address calculation unit302to obtain data corresponding to the second packet.

Packet reconstruction unit304generates a new data packet by incorporating therein these two data obtained by memory access unit303. For example, packet reconstruction unit304writes the obtained data corresponding to the first packet in a data region of data0in the first packet, and writes the obtained data corresponding to the second packet in a data region of data1to generate the new data packet.

As for the conventional data-driven information processing device as discussed above, if two data included in the data packet indicate address information of the table memory, memory access unit303accesses the table memory according to the address information for each data, resulting in a problem that two cycles are required and the throughput of the entire data-driven information processing device is accordingly decreased. This problem becomes serious as the number of data included in the data packet increases. Moreover, a similar problem occurs when memory access unit303writes the data stored in the data packet into the table memory.

SUMMARY OF THE INVENTION

One object of the present invention is to provide data-driven information processing device and method to improve processing rate for a data packet including a plurality of data.

Another object of the present invention is to provide versatile data-driven information processing device and method for accessing bank memories by changing an access method depending on the type of a program to be processed.

According to one aspect of the present invention, a data-driven information processing device processing a data packet including a plurality of data includes a plurality of bank memories, an address calculation unit calculating a plurality of addresses corresponding respectively to a plurality of data included in the data packet, an access unit accessing the bank memories according to the addresses calculated by the address calculation unit, and a reconstruction unit reconstructing the data packet according to the result of the access by the access unit.

The access unit accesses a plurality of bank memories according to a plurality of addresses calculated by the address calculation unit. Accordingly, the processing rate for the data packet including a plurality of data is increased.

According to another aspect of the present invention, a method of processing a data packet including a plurality of data by a data-driven information processing device includes the steps of calculating a plurality of addresses corresponding respectively to those plurality of data included in the data packet, accessing a plurality of bank memories according to the calculated addresses, and reconstructing the data packet according to the result of the access.

As a plurality of bank memories are accessed according to a plurality of calculated addresses, the processing rate for the data packet including a plurality of data is increased.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

First Embodiment

A data-driven processor according to a first embodiment of the present invention has its general configuration differing from that of the conventional data-driven processor shown inFIG. 2only in the configuration and function of the memory access control unit. Detailed description of the configurations and functions common to these processors is not repeated here. It is noted that a memory access control unit of this embodiment is denoted by reference numeral10and accordingly described.

In addition, a data packet processed by a data-driven information processing device according to the first embodiment of the present invention has its structure similar to that of the data packet processed by the conventional data-driven information processing device shown inFIG. 1, and detailed description thereof is not repeated here.

FIG. 4is a block diagram showing a configuration of memory access control unit10according to the first embodiment of the present invention. Memory access control unit10includes an address calculation unit11, a first bank memory access unit12, a second bank memory access unit13and a packet reconstruction unit14.

The first bank memory access unit12is connected to a first bank memory (not shown) to access the first bank memory according to an address supplied from address calculation unit11. The first bank memory has a data width of 16 bits and is constituted of 128 words.

The second bank memory access unit13is connected to a second bank memory (not shown) to access the second bank memory according to an address supplied from address calculation unit11. The second bank memory has a data width of 16 bits and is constituted of 128 words.

Address calculation unit11receives a data packet as shown inFIG. 1to calculate respective addresses of data to be accessed with reference to data0(106) and data1(107). The addresses of the data are respectively calculated according to the following expressions where “&” represents a logical product or AND, and “+” represents a logical sum or OR.
address of data 0=data 0 & mask value  (1)
address of data 1=(data 1 & mask value)+offset value  (2)

The mask value masks upper bits (bit7–bit15) of the address and is 0x007F. The logical product of data0or data1and the mask value is determined to indicate an address within one bank memory. Here, “0x” indicates that numerals following this symbol are represented in hexadecimal notation.

The offset value indicates the size of one bank memory and is 0x80. In calculation of the address of data1, the offset value is added to allow the second bank memory access unit13to access the second bank memory without fail. As no offset value is added to the address of data0, the first bank memory access unit12accesses the first bank memory without fail.

Address calculation unit11outputs the determined addresses respectively of data0and data1simultaneously to the first bank memory access unit12and the second bank memory access unit13. According to respective addresses of data0and data1, the first bank memory access unit12and the second bank memory access unit13simultaneously access the first and second bank memories respectively.

Packet reconstruction unit14stores the result of access by the first bank memory access unit12in the field of data0(106) of the data packet shown inFIG. 1and stores the result of access by the second bank memory access unit13in the field of data1(107) of the data packet shown inFIG. 1. In this way, one reconstructed data packet is output from packet reconstruction unit14.

For example, the first bank memory and the second bank memory may be used as look-up tables. The first and second bank memories are initialized to include exactly the same contents, and the first and second bank memories are used for determining value Y from value X as indicated by the following expression.
Y=function (X)  (3)

Value X ranges from 0x00 to 0x7F. According to value X stored in the fields of data0(106) and data1(107) of the data packet shown inFIG. 1, value Y is read from each of the first and second bank memories. Memory access control unit10thus obtains two Y values simultaneously in one cycle.

The first and second bank memories may be used as counters. In this case, values written into the first and second bank memories are all initialized to 0. Specifically, if the first and second bank memories each have a capacity of 128 words, the memories function each as a maximum of 128 counters. Respective count values are all initialized to 0.

If instruction information104included in the data packet shows that the count value should be incremented, the first bank memory access unit12and the second bank memory access unit13read respective values from the first bank memory and the second bank memory according to the address of data0and the address of data1, and then increment the read values by 1 and write the values at the same addresses in the first bank memory and the second bank memory. This process is indicated by the following expression, where X represents the value (address) of data0or of data1.
table (X)=table (X)+1  (4)

When the count-up is completed, the count value of the address in the first bank memory and the count value of the address in the second bank memory corresponding to the relevant counters are added together to generate a value of the counters. The counters are used for calculation of the number of times operation is performed in the data-driven information processing device or the number of times the data packet is cycled, for example.

As the first bank memory access unit12and the second bank memory access unit13thus simultaneously access the first and second bank memories respectively, the two counter values are incremented in one cycle and thus the processing rate of the data-driven information processing device is improved.

The data-driven information processing device of this embodiment has been described as having two bank memories. The data-driven information processing device may also be implemented by being provided with three or more bank memories.

As discussed above, in the data-driven information processing device of the first embodiment of the present invention, the first bank memory access unit12and the second bank memory access unit13access respective bank memories different from each other according to data0(106) and data1(107) in the data packet. Accordingly, access to multiple addresses in one cycle is possible, which improves the throughput of the entire data-driven information processing device and increase the processing rate.

Second Embodiment

A data-driven processor according to a second embodiment of the present invention has its general configuration differing from that of the conventional data-driven processor shown inFIG. 2only in the configuration and function of the memory access control unit. Detailed description of the configurations and functions common to these processors is not repeated here. It is noted that a memory access control unit of this embodiment is denoted by reference numeral40and accordingly described.

The data-driven information processing device of the first embodiment accesses a plurality of addresses (data0, data1) included in the data packet in one cycle to increase the processing rate. Although the processing rate is improved, it is required to store the same contents in a plurality of bank memories and accordingly the bank memories used here must have a greater capacity.

The data-driven information processing device is applicable to various uses by changing a program to be executed and thus may be used for an application requiring a high processing rate or for an application using many bank memories while a high processing rate is unnecessary. The data-driven information processing device of this embodiment is applicable to these uses.

FIG. 5schematically shows a structure of a data packet processed by the data-driven information processing device according to the second embodiment of the present invention. The data packet includes a tag section20and a data section21. Tag section20includes destination information22indicating a node number in a program, instruction information23indicating the type of operation performed on a plurality of data included in data section21, memory access information24indicating the way in which access is made to a bank memory as described hereinbelow, and effective data information25indicating which of the data included in data section21is effective. The field in which memory access information24is stored may be allocated to a predetermined register instead of tag section20.

Data section21includes data0(26), data1(27), data2(28) and data3(29). In this embodiment, data0–data3(26–29) each have a data width of 16 bits.

FIGS. 6A–6Ceach show a structure of bank memories according to the second embodiment of the present invention. A first bank memory31, a second bank memory32, a third bank memory33and a fourth bank memory34each have a data width of 16 bits and is constituted of 128 words.

FIG. 6Ashows a structure of the bank memories when memory access information24shown inFIG. 5indicates “0.” When memory access information24is “0,” memory access control unit40simultaneously accesses first bank memory31–fourth bank memory34to obtain 4 words (16 bits×4) of data at a time.

FIG. 6Bshows a structure of the bank memories when memory access information24shown inFIG. 5indicates “1.” When memory access information24is “1,” memory access control unit40regards the first and second bank memories31and32as one bank memory and regards the third and fourth bank memories33and34as one bank memory. In other words, the first and second bank memories31and32are regarded as one bank memory having a 16-bit data width and storing 256-word data. Similarly, the third and fourth bank memories33and34are regarded as one bank memory having a 16-bit data width and stores 256-word data. Memory access control unit40thus simultaneously accesses two of the first to fourth bank memories31–34to obtain 2-word (16 bits×2) data at a time.

FIG. 6Cshows a structure of the bank memories when memory access information24shown inFIG. 5indicates “2.” When memory access information24is “2,” memory access control unit40regards the first to fourth bank memories31–34as one bank memory. In other words, the first to fourth bank memories31–34are regarded as one bank memory having a 16-bit data width and stores 512-word data. Then, memory access control unit40accesses one of the first to fourth bank memories31–34to obtain one word (16 bits) data.

Memory access information24thus indicates the number of bank memories that are simultaneously accessed by memory access control unit40as well as the number of data packets to be copied and output as described hereinbelow.

FIG. 7is a block diagram showing a configuration of memory access control unit40according to the second embodiment of the present invention. Memory access control unit40includes a packet copy unit41, an address calculation unit42, a first bank memory access unit43, a second bank memory access unit44, a third bank memory access unit45, a fourth bank memory access unit46and a packet reconstruction unit47.

The first bank memory access unit43is connected to the first bank memory31shown inFIGS. 6A–6Cto access the first bank memory31according to an address supplied from address calculation unit42. The second bank memory access unit44is connected to the second bank memory32shown inFIGS. 6A–6Cto access the second bank memory32according to an address supplied from address calculation unit42.

The third bank memory access unit45is connected to the third bank memory33shown inFIGS. 6A–6Cto access the third bank memory33according to an address supplied from address calculation unit42. The fourth bank memory access unit46is connected to the fourth bank memory34shown inFIGS. 6A–6Cto access the fourth bank memory34according to an address supplied from address calculation unit42.

If packet copy unit41receives a data packet including memory access information24indicating “0,” packet copy unit41does not copy the data packet. In this case, four addresses are accessed in one cycle.

If packet copy unit41receives a data packet including memory access information24indicating “1,” packet copy unit41copies the data packet to generate two data packets. One of the two data packets has its data sections21storing data0and data1while the other of the two data packets has its data section21storing data2and data3. These two data packets are supplied in order to address calculation unit42. In this case, four addresses are accessed in two cycles.

If packet copy unit41receives a data packet including memory access information24indicating “2,” packet copy unit41copies the data packet to produce four data packets. The four data packets have respective data sections21storing data0–data3respectively. These four data packets are supplied in order to address calculation unit42. In this case, four addresses are accessed in four cycles.

If memory access information24included in a received data packet is “0,” address calculation unit42refers to data0–data3(26–29) to calculate respective addresses of the data to be accessed. Respective addresses of the data are calculated by the following expressions.
address of data 0=data 0 & mask value  (5)
address of data 1=(data 1 & mask value)+offset value  (6)
address of data 2=(data 2 & mask value)+offset value×2  (7)
address of data 3=(data 3 & mask value)+offset value×3  (8)

The mask value masks upper bits (bit7–bit15) of the address and is 0x7F. The logical products of data0–data3and the mask value are determined and accordingly an address within one bank memory is designated.

The offset value represents the size of one bank memory and is 0x80. In calculation of the addresses of data1–data3, the offset value is added to allow the second to fourth bank memories32–34to be accessed without fail. As no offset value is added to the address of data0, the first bank memory31is accessed without fail.

If memory access information24included in a received data packet is “1,” address calculation unit42refers to data0and data1(26,27) included in the first data packet to calculate respective addresses of the data to be accessed. Respective addresses of the data are calculated by the following expressions.
address of data 0=data 0 & mask value  (9)
address of data 1=(data 1 & mask value)+offset value  (10)

The mask value masks upper bits (bit8–bit15) of the address and is 0x00FF. The logical products of data0and data1and the mask value are determined and thus an address within one bank memory is designated.

The offset value represents the size of one bank memory and is 0x100. In calculation of the address of data1, the offset value is added to allow the third bank memory33or the fourth bank memory34to be accessed without fail. As no offset value is added to the address of data0, the first bank memory31or the second bank memory32is accessed without fail.

If bit7of the address of data0calculated by expression (9) is “0,” the first bank memory access unit43accesses the first bank memory31. If bit7of the address of data0is “1,” the second bank memory access unit44accesses the second bank memory32.

If bit7of the address of data1calculated by expression (10) is “0,” the third bank memory access unit45accesses the third bank memory33. If bit7of the address of data1is “1,” the fourth bank memory access unit46accesses the fourth bank memory34.

Then, address calculation unit42refers to data2and data3(28,29) included in the second data packet to calculate respective addresses of the data to be accessed. Respective addresses of the data are calculated by the following expressions.
address of data 2=data 2 & mask value  (11)
address of data 3=(data 3 & mask value)+offset value  (12)

The mask value is 0x00FF. The logical products of data2and data3and the mask value are determined to indicate an address within one bank memory. The offset value is 0x100. In calculation of the address of data3, the offset value is added to allow the third bank memory33or the fourth bank memory34to be accessed without fail. As no offset value is added to the address of data2, the first bank memory31or the second bank memory32is accessed without fail.

If bit7of the address of data2calculated by expression (11) is “0,” the first bank memory access unit43accesses the first bank memory31. If bit7of the address of data2is “1,” the second bank memory access unit44accesses the second bank memory32.

If bit7of the address of data3calculated by expression (12) is “0,” the third bank memory access unit45accesses the third bank memory33. If bit7of the address of data3is “1,” the fourth bank memory access unit46accesses the fourth bank memory34.

If address calculation unit42receives a data packet having memory access information24indicating “2,” address calculation unit42refers to data0(26) included in the first data packet to calculate the address of the data to be accessed. The address of data0is calculated by the following expression.
address of data 0=data 0 & mask value  (13)

The mask value masks upper bits (bit9–bit15) of the address and is 0x01FF. Here, no offset value is used.

If bit7and bit8of the address of data0calculated by expression (13) indicate “00,” the first bank memory access unit43accesses the first bank memory31. If bit7and bit8of the address of data0indicate “01,” the second bank memory access unit44accesses the second bank memory32. If bit7and bit8of the address of data0indicate “10,” the third bank memory access unit45accesses the third bank memory33. If bit7and bit8of the address of data0indicate “11,” the fourth bank memory access unit46accesses the fourth bank memory34.

Then, address calculation unit42refers to data1(27) included in the second data packet to calculate the address of the data to be accessed. The address of data1is calculated by the following expression. As done for data0, according to bit7and bit8of the address of data1, any of the first to fourth bank memory access units43–46accesses the corresponding bank memory.
address of data 1=data 1 & mask value  (14)

Then, address calculation unit42refers to data2(28) included in the third data packet to calculate the address of the data to be accessed. The address of data2is calculated by the following expression. As done for data0, according to bit7and bit8of the address of data2, any of the first to fourth bank memory access units43–46accesses the corresponding bank memory.
address of data 2=data 2 & mask value  (15)

Finally, address calculation unit42refers to data3(29) included in the fourth data packet to calculate the address of the data to be accessed. The address of data3is calculated by the following expression. As done for data0, according to bit7and bit8of the address of data3, any of the first to fourth bank memory access units43–46accesses the corresponding bank memory.
address of data 3=data 3 & mask value  (16)

If packet reconstruction unit47receives a data packet having memory access information24of “0,” four results of the access are directly incorporated in one data packet to be output.

If packet reconstruction unit47receives a data packet having memory access information24of “1,” packet reconstruction unit47extracts the access results of data0(26) and data1(27) from the first data packet and extracts the access results of data2(28) and data3(29) from the second data packet to incorporate the access results in one data packet to be output.

If packet reconstruction unit47receives a data packet having memory access information24of “2,” packet reconstruction unit47extracts the access result of data0(26) from the first data packet, the access result of data1(27) from the second data packet, the access result of data2(28) from the third data packet, and the access result of data3(29) from the fourth data packet to incorporate the access results in one data packet to be output.

As heretofore discussed, the data-driven information processing device according to this embodiment calculates the address by address calculation unit42changing the way to calculate the address depending on the value of memory access information24. According to the calculated address, the first to fourth bank memory access units43–46access the bank memories. Depending on the type of program, the processing rate may be increased or the capacity of the bank memory used here may be increased. The versatile data-driven information processing apparatus is thus provided