Distributed shared memory multiprocessor and data processing method

A distributed shared memory multiprocessor that includes a first processing element, a first memory which is a local memory of the first processing element, a second processing element connected to the first processing element via a bus, a second memory which is a local memory of the second processing element, a virtual shared memory region, where physical addresses of the first memory and the second memory are associated for one logical address in a logical address space of a shared memory having the first memory and the second memory, and an arbiter which suspends an access of the first processing element, if there is a write access request from the first processing element to the virtual shared memory region, according to a state of a write access request from the second processing element to the virtual shared memory region.

BACKGROUND

1. Field of the Invention

The present invention relates to a distributed shared memory multiprocessor and a data processing method of the same.

2. Description of Related Art

In recent years, the processing speed of a single processor is approaching the limit and a multiprocessor, which uses multiple processors performing parallel processes, is highlighted and is already in practical application. A multiprocessor is usually provided with a shared memory for multiple processors to access each other. Such multiprocessor is referred to as a shared memory multiprocessor. Further, the shared memory multiprocessors can be roughly divided into a centralized shared memory type where multiple processors are connected to one shared memory, and a distributed shared memory type where multiple processors each have local memories.

FIG. 6is a pattern diagram of a distributed shared memory multiprocessor to explain the problem to be solved by the present invention. Each of processor elements PE1and PE2provided with CPUs respectively includes local memories LM1and LM2. Further, the processor elements PE1and PE2are connected via a bus. Therefore, the processor element PE1can also access the local memory LM2, and the processor element PE2can also access the local memory LM1.

Accordingly, the local memories LM1and LM2are shared by the two processor elements PE1and PE2, and are placed at one logical address space. In such distributed shared memory multiprocessor, a processor element can access its own local memory at high speed. On the other hand, it takes time to access local memories of other processor elements as multiple steps of bridges are routed through. Writing can be carried out at relatively high speed by posted write, thus the problem is the time taken for reading out.

In response, Japanese Unexamined Patent Application Publication No. 5-290000 discloses a distributed shared memory multiprocessor which defines a broadcast region in a logical address space. The broadcast region is a region recognized as the same address region by each processor element. On the other hand, the region is actually the region storing the same data in each local memory. If there is a write request to the broadcast region, the same data is written to each local memory. Further, if there is a read request to the broadcast region, data is read out from the own local memory. Thus data can be read out at high speed.

SUMMARY

However, the present inventor has found a problem that in the distributed shared memory multiprocessor disclosed in Japanese Unexamined Patent Application Publication No. 5-290000, there is a difference in the timings to complete writing to the own local memory and complete writing to the local memories of other processors. Therefore, there could be an inconsistency in the data of each local memory, which should be the same.

For example, a case is described hereinafter, in which there are write requests at the same time from the processor elements PE1and PE2to the same address in the broadcast region. In such case, the request from the processor element PE1reaches the local memory LM1first, and then reaches the local memory LM2. Further, the request of the processor element PE2reaches the local memory LM2first, and then reaches the local memory LM1.

Therefore, data is written to the local memory LM1first by the processor element PE1, and then rewritten by the processor element PE2. On the other hand, data is written to the local memory LM2first by the processor element PE2, and then rewritten by the processor element PE1. Thus, there is an inconsistency generated in the data written to the local memories LM1and LM2.

In the abovementioned case, the write requests from each processor element are not competitive in memory interfaces MIF1and MIF2. Accordingly, the abovementioned data inconsistency cannot be prevented by arbiters (not shown) provided to the memory interfaces MIF1and MIF2.

A first exemplary aspect of the present invention is a distributed shared memory multiprocessor that includes a first processing element, a first memory which is a local memory of the first processing element, a second processing element connected to the first processing element via a bus, a second memory which is a local memory of the second processing element, a virtual shared memory region, where physical addresses of the first memory and the second memory are associated for one logical address in a logical address space of a shared memory having the first memory and the second memory, and an arbiter which suspends an access of the first processing element, if there is a write access request from the first processing element to the virtual shared memory region, according to a state of a write access request from the second processing element to the virtual shared memory region.

The present invention provides a distributed shared memory multiprocessor which is capable of high-speed reading and also prevents inconsistencies in the data between the local memories.

DETAILED DESCRIPTION OF THE EXEMPLARY EMBODIMENTS

Hereafter, specific exemplary embodiments incorporating the present invention are described in detail with reference to the drawings. However, the present invention is not necessarily limited to the following exemplary embodiments. The explanation and drawings below are simplified as appropriate for clarity of explanation.

First Exemplary Embodiment

Hereinafter, an exemplary embodiment of the present invention is described with reference to the drawings.FIG. 1is a block diagram of a distributed shared memory multiprocessor according to a first exemplary embodiment. As shown inFIG. 1, the multiprocessor according to the first exemplary embodiment includes a processor element PE1, a processor element PE2, a local memory LM1, a local memory LM2, and a synchronous window arbiter100. Note that this exemplary embodiment is a typical example of a distributed shared memory multiprocessor provided with a plurality of processors and a local memory for each of the processors, and needless to say, that the numbers of the processors and the local memories are not limited to two.

The processor element PE1includes a CPU1, a RAM interface MIF11, and a RAM interface between PEs MIF12. The CPU1is connected to the RAM interface between PEs MIF11and the RAM interface between PEs MIF12via a bus. The RAM interface MIF11is connected to the local memory LM1, which is a local RAM of the processor element PE1, via a bus. Thus the CPU1can access the local memory LM1.

The processor element PE2includes a CPU2, the RAM interface MIF12, and a RAM interface between PEs MIF22. The CPU2is connected to the RAM interface MIF21and the RAM interface between PEs MIF22via a bus. The RAM interface MIF21is connected to the local memory LM2, which is a local RAM of the processor element PE2, via a bus. Thus the CPU1can access the local memory LM2.

Further, the RAM interface between PEs MIF12of the processor element PE1is connected to the RAM interface MIF21of the processor element PE2via a bus. Thus the CPU1can also access the local memory LM2. On the other hand, the RAM interface between PEs MIF22of the processor element PE2is connected to the RAM interface MIF11of the processor element PE1via a bus. Thus the CPU2can also access the local memory LM1.

In this way, the local memories LM1and LM2are shared by the two processor elements PE1and PE2, and are placed at one logical address space. Further, the distributed shared memory multiprocessor according to the first exemplary embodiment includes a virtual shared memory region, which is recognized as the same address region by the processor elements PE1and PE2. Such memory region is referred to as a synchronous window region in this document. The abovementioned region is referred to as the broadcast region in Japanese Unexamined Patent Application Publication No. 5-290000.

The synchronous window region is actually the region to store the same data in each local memory. If there is a write request to the synchronous window region, the same data is written to each local memory. Further, if there is a read request to the synchronous window region, data is read out from the own local memory. This enables a high-speed reading.

The synchronous window region is described in further detail with reference toFIGS. 2A to 2C.FIG. 2Ais a memory map image of a shared memory in the distributed shared memory multiprocessor according to the first exemplary embodiment. As shown in the memory map ofFIG. 2A, a memory region (PE1-RAM inFIG. 2A) of the local memory LM1, which is a local RAM of the processor element PE1, a memory region (PE2-RAM inFIG. 2A) of the local memory LM2, which is a local RAM of the processor element PE2, and the synchronous window region are defined.

InFIG. 2A, the capacities of the three regions are all 2 MB. The synchronous window region is specified by logical addresses FEE00000 to FEFFFFFF. The local memory region PE1-RAM is specified by logical addresses FEC00000 to FEDFFFFF. The local memory region PE2-RAM is specified by logical addresses FEA00000 to FEBFFFFF.

FIG. 2Billustrates a case when there is a write request from the processor element PE1. For example, if there is a write request from the processor element PE1to the logical address FEE00100 of the synchronous window region, the same data is written to the physical address 00100 of the local memory region PE1-RAM and the local memory region PE2-RAM. The similar operation is carried out for a write request from the processor element PE2.

FIG. 2Cillustrates a case when there is a read request from the processor element PE1. For example, if there is a read request to the logical address FEE00100 of the synchronous window region from the processor element PE1, data is read out from the physical address 00100 of the own local memory region PE1-RAM. Note that similarly for a read request from the processor element PE2, data is read out from the own local memory region PE2-RAM.

The synchronous window arbiter100is responsible for arbitrating between a write access from the processor element PE1and a write access from the processor element PE2. No arbitration is needed for a read access, as each processor element only accesses to its own local memory. The synchronous window arbiter100includes a PE1control unit110and a PE2control unit120. The PE1control unit110and the PE2control unit120respectively include a PE1address buffer111and a PE2address buffer121.

An operation is described hereinafter when there is a write access request from the processor element PE1with reference toFIG. 1. In the case of a write access, the RAM interface MIF11outputs an access request to the PE1control unit110of the synchronous window arbiter100. Further, access information, such as a target address, a lock request, and an access type (read/write), is also input to the PE1control unit of the synchronous window arbiter100from the RAM interface MIF11. The target address is registered to the PE1address buffer111. Note that if there is only a read access, an access request will not be output from the RAM interface MIF11. However in case of an atomic access that includes both reading and writing such as read-modify-write, the RAM interface MIF11outputs an access request.

If the same address as the access request address is not registered to the PE2address buffer121, the synchronous window arbiter100immediately outputs an access permission to the processor element PE1. On the other hand, if the same address as the access request address is registered to the PE2address buffer121, the synchronous window arbiter100outputs an access permission to the processor element PE1after the PE2address buffer121is released. That is, first access request is prioritized. This access permission is input to the RAM interface MIF11and the RAM interface between PEs MIF12.

Then, in response to an access completion notification from the RAM interface between PEs MIF12of the processor element PE1, the PE1address buffer111is released. The same operation is carried out for an access request from the processor element PE2. If there are access requests at the same time from the processor elements PE1and PE2, the access order may be determined according to a predetermined agreement. In this embodiment, the processor element permitted last time is kept wait.

As described above, a writing access from each processor element obtains a permission from the synchronous window arbiter100to be processed. Therefore, there is no inconsistency generated in the data that should be the same.

FIG. 3is a detailed block diagram of the synchronous window arbiter100. The synchronous window arbiter100includes a PE1control unit110, a PE2control unit120, and a control unit between PEs130. Further, the PE1control unit110includes an address buffer111, an access permission control unit112, a suspension evaluation unit113, an address buffer control unit114, and a comparator115.

The access permission control unit112is connected to the suspension evaluation unit113and the address buffer control unit114. The address buffer control unit114is connected to the address buffer111. There are three address buffers111provided inFIG. 3. Further, three comparators115are also provided. Each address buffer111is respectively connected to each comparator115. The number of the address buffers is preferably the same as the number of buffers included in the RAM interfaces MIF12and MIF22. The number of the buffers is not limited to three, however it should preferably be multiple steps in order to enable to register multiple addresses. The details of the PE2control unit120are same as the PE1control unit110, thus the explanation is omitted.

The operation of the synchronous window arbiter100is described in detail with reference toFIG. 3. Hereinafter, a case is described, in which access requests from the processor element PE1and the processor element PE2are not simultaneous. An access with a lock is described later. The control unit between PEs130does not concern as the access requests from the processor element PE1and the processor element PE2are not simultaneous.

Firstly, a read/write signal and an address (address) signal are input to the PE1control unit110along with an access request signal from the processor element PE1. The access request is input to the access permission control unit112. The read/write signal is input to the access permission control unit112and the address buffer control unit114. The address signal is input to the address buffer111. Further, this address signal (PE1address signal) is input also to the processor element PE2.

In response to the access request, the access permission control unit112outputs a buffer set signal to the address buffer control unit114and the suspension evaluation unit113. The address buffer control unit114outputs a buffer registration signal (PE1buffer registration signal) to the address buffer111according to the buffer set signal. This enables a request address to be registered to the address buffer111. Further, the PE1buffer registration signal output from the address buffer control unit114is input also to the suspension evaluation unit113of the processor element PE2, and is used for the suspension evaluation in the processor element PE2.

On the other hand, the buffer set signal triggers the suspension evaluation unit113to generate a suspension evaluation signal of either “permitted” or “suspended” according to a PE2address match signal, a PE2buffer registration signal, and a PE2buffer release signal, which are input from the processor element PE2. Specifically, if the address registered to the address buffer121of the processor element PE2matches the access request address from PE1, the signal is “suspended”, otherwise the signal is “permitted”. This signal is input to the access permission control unit112. If the access is permitted, the access permission control unit112outputs an access permission signal to the processor element PE1. Furthermore, the access permission control unit112outputs a permission status notification to the control unit between PEs130.

At a completion of accesses to both of the local memories, an access completion notification is input to the address buffer control unit114. In response to the access completion notification, the address buffer control unit114outputs a buffer release signal (PE1buffer release signal) to the address buffer111. Then the address buffer111where the address is registered is released. Further, the PE1buffer release signal output from the address buffer control unit114is input also to the suspension evaluation unit113of the processor element PE2, and is used for suspension evaluation in the processor element PE2.

The address registered to the address buffer111is input to the comparator115. If there is an access request of the processor element PE2, the comparator115compares the address (PE2address signal) with the address registered to the address buffer111, and generates a PE1address match signal. This signal is input to the suspension evaluation unit113of the processor element PE2, and is used for suspension evaluation in the processor element PE2.

Next, a case is described, in which access requests from the processor elements PE1and PE2are simultaneous. An access with a lock is described later. In this case, the control unit between PEs130concerns as the access requests from the processor elements PE1and PE2are simultaneous.

The PE1address signal and the PE2address signal are input to the control unit between PEs130. The buffer set signal and the permission state notification are input to the control unit between PEs130from the processor elements PE1and PE2. The control unit between PEs130can determine whether the access requests are simultaneous based on the buffer set signal from the processor elements PE1and PE2. Further, the control unit130can determine whether the access request address matches according to the PE1address signal and the PE2address signal.

If the access requests are simultaneous and also the addresses of the accesses match, the control unit between PEs130outputs an address match signal and a priority notification to the processor elements PE1and PE2. The priority notification indicates the priority of the processor elements to be permitted, and is generated according to the permission state notification. In this embodiment, the processor element permitted last time is kept wait and the other one is permitted. The address match signal and the priority notification are input to the suspension evaluation unit113of each processor element. The suspension evaluation unit113generates a suspension evaluation signal based on such information. Other operations are same as the operation when the accesses are not simultaneous.

An access with a lock is described hereinafter. If there is an access request with a lock from the processor element PE1, a lock signal is input to the PE1control unit110in addition to the access request signal, the read/write signal, and the address signal. To be more specific, the lock signal is input to the address buffer control unit114. The address buffer control unit114outputs a lock request (PE1lock request) based on the lock signal. The lock request is input to the address buffer111. In this case, the comparator115outputs the address match signal, indicating a match of the addresses. The PE1lock request is input also to the comparator115of the PE2control unit.

On the other hand, if there is an access request with a lock from the processor element PE2, the lock request (PE2lock request) from the processor element PE2is input to the comparator115of the processor element PE1. Also in this case, the comparator115outputs the address match signal, indicating a match of the addresses.

Further, the PE1lock request and the PE2lock request are input also to the control unit between PE130. Therefore, if there are access requests simultaneously and at least one of them requires a lock, the control unit between PEs130regards that the addresses match and outputs the address match signal.

As described above, as for write access requests with a lock, the addresses are regarded to match even if the access request address from the other processor do not match the address. When trying to perform a competitive evaluation of related access addresses for an atomic access with a lock, hardware configuration required for the address evaluation becomes complicated. However this exemplary embodiment achieves a simple hardware configuration. An atomic access with a lock originally suspends accesses from other processor elements by a lock. Thus there are few disadvantages for the processing speed by the abovementioned processes.

Next, the operation is explained with reference to the timing charts ofFIGS. 4 and 5, andFIG. 1.FIG. 4illustrates a case in which the processor element PE1issues a write request and the processor element PE2issues a read request to the same address in the synchronous window region. In order to read, accesses are made only to the own local memories. Therefore no access permission is required. Thus the CPU2of the processor element PE2does not wait and reads out data from the own local memory LM2via the RAM interface MIF21. Then the operation is completed.

On the other hand, the CPU1of the processor element PE1issues an access request to the synchronous window arbiter100via a data bus. Then, an access request address is registered to the address buffer111for the processor element PE1. In the example ofFIG. 4, there is no competition generated, as the request from the processor element PE2is a read. Accordingly, an access permission is immediately output from the synchronous window arbiter100. The CPU1writes data to the own local memory LM1via the RAM interface MIF11according to the access permission. Further, a write request is issued to the RAM interface between PEs MIF12by posted write method. Then the operation of the CPU1is completed.

After that, the data held in the RAM interface between PEs MIF12is written to the local memory LM2via the RAM interface MIF21of the processor element PE2. Then the operation of the RAM interface between PEs MIF12is completed. After that, the address buffer111for the processor element PE1is released.

FIG. 5is a timing chart when the processor elements PE1and PE2issue write requests to the same address in the synchronous window region. Moreover,FIG. 5illustrates a case in which the access requests are issued at the same time and the processor element PE1is prioritized. Note that this applies to when an access from the processor element PE1is issued first.

The CPU1of the processor element PE1issues an access request to the synchronous window arbiter100via a data bus. Then, an access request address is registered to the address buffer111for the processor element PE1. On the other hand, the CPU2of the processor element PE2issues an access request to the synchronous window arbiter100via a data bus. Then, an access request address is registered to the address buffer121for the processor element PE2.

In the example ofFIG. 5, a competition is generated, as the requests from both processor elements are write. First, the synchronous window arbiter100outputs an access permission to the processor element PE1. The CPU1writes data to the own local memory LM1via the RAM interface MIF11according to the access permission. Further, a write request is made to the RAM interface between PEs12by the posted write method. Then the operation of the CPU1is completed.

After that, the data held in the RAM interface between PEs MIF12is written to the local memory LM2via the RAM interface MIF21of the processor element PE2. Then the operation of the RAM interface between PEs MIF12is completed. Then, the address buffer111for the processor element PE1is released.

If the abovementioned address buffer111is released, the access permission for the processor element PE2suspended till then is output from the synchronous window arbiter100. The CPU2writes data to the own local memory LM2via the RAM interface MIF21according to the access permission. Further, a write request is made to the RAM interface between PEs MIF22by the posted write method. Then the operation of the CPU2is completed.

After that, the data held in the RAM interface between PEs MIF22is written to the local memory LM1via the RAM interface MIF11of the processor element PE1. Then the operation of the RAM interface between PEs MIF22is completed. Then, the address buffer121for the processor element PE2is released.

As described above, the distributed shared memory multiprocessor according to the exemplary embodiment of the present invention is capable of high-speed readout by the synchronous window included therein. Further, as the synchronous window arbiter100is included, no inconsistency is generated in the data stored in each local memory that should be the same. Furthermore, the multiprocessor determines that a competition is generated only for write requests with access request addresses matched, thereby keeping the opportunity for suspension to the minimum and enabling high-speed processes. Moreover, an access request with a lock is considered that the addresses are matched, and this enables to eliminate hardware necessary for address evaluation of related accesses and also achieve a simple configuration.

While the invention has been described in terms of several exemplary embodiments, those skilled in the art will recognize that the invention can be practiced with various modifications within the spirit and scope of the appended claims and the invention is not limited to the examples described above.