JP2009048306A - Parallel processing architecture and parallel processing processor using the same - Google Patents

Abstract

A parallel processing processor is configured by an FPGA, and a program process is processed in parallel in a single processor.
A processor is provided with a process management register, a general-purpose internal stack register, and a memory, a process identification number of a program to be executed is managed by the process management register and the memory, and the process identification number is linked on the memory. By forming the scheduling list in the structure, the processes are connected to each other, and process switching and channel communication between processes are executed.
[Selection] Figure 1

Description

  The present invention relates to a central processing unit (CPU) that is the core of a computer system, and performs a parallel processing by itself, and further performs a parallel processing architecture that performs parallel processing while synchronizing with a plurality of CPUs by cooperation or data exchange. The present invention relates to the parallel processor used.

In the late 1980s and early 1990s, a processor for parallel processing (Transputer (registered trademark)) based on CSP (Communicating Sequential Processes) theory was developed and sold by UK company INMOS. This transputer worked in conjunction on multiple networks, where it demonstrated its capabilities and increased computation speed. However, the development, production and sales of this transputer were discontinued.
In addition, in the VLSI (Large Scale Integrated Circuit) technology of the mid-1980s, a circuit on the scale of one transputer occupies a place and space that completely occupies one VLSI chip. The network was realized with a huge board (circuit board). In addition, each interface was realized with several wires connecting the chips.
On the other hand, only a rough architecture block diagram is disclosed as a document about the transputer, and a parallel processing algorithm related to the inside of the single unit of the transputer has not been disclosed.

  In the CSP theory described above, a certain calculation system (program) is regarded as a set of processes, and the processes are synchronized by performing message communication with each other, and the calculation is executed. In addition, the process indicates “the actual situation in which a certain action is continuously executed sequentially”. In addition, a plurality of processes operate independently at the same time in a program, and the processes communicate with each other via input / output operations executed inside the process. This communication enables synchronization between processes. In other words, when one process reaches the input (output) operation processing stage, it waits for the other process to reach the corresponding output (input) operation stage, and communication is executed when they reach each other's data (message) communication stage. . Data to be input / output is exchanged without being stored or buffered in a queue (queue). Thus, the processing between the two processes is aligned. Then, after the communication is completed, the original process is continued again.

In the CSP theory described above, there is no shared memory for two processes or all processes that communicate with each other, and data is shared between processes only by inter-channel communication.
There is Occam (registered trademark) as a programming language that embodies CSP theory, and a program written in this language is regarded as a set of processes that are processed (running) in parallel. Data exchange between two processes running in parallel is performed using the concept of channel, and a common channel variable is defined in the two processes, and data exchange and synchronization are performed through this.
Patent Document 1 discloses a configuration in which a plurality of transputers are connected using a switch, and Patent Document 2 discloses an example of a data parallel processing method applied to image processing using an external frame. is there. Non-Patent Document 1 discloses a register structure of a processor, but does not disclose a detailed structure of a single processor or an architecture for executing processes in parallel.

Japanese Unexamined Patent Publication No. 63-501986 JP-A-3-263164 Introduction to Transputer; Masaki Yamamoto, Yasuaki Nakai, Annori Murakami; Nikkan Kogyo Shimbun

A transputer produced based on the excellent information science theory CSP theory functions only in the programming language Occam based on the CSP theory. Therefore, Occam is indispensable for research and development of CSP theory. However, since there is no transputer that operates using it, there has been a big problem in theoretical development and its practical application.
Transputer development was discontinued, but the need for parallel processors based on CSP theory was only growing. In addition, VLSI CMOS (Complementary Metal Oxide Semiconductor) packaging technology in the transputer development era has a big difference with modern technology, and the physical scale of the VLSI was full with only one processor at that time. In addition, CMOS transistors have been miniaturized and about 20 processors can be mounted. When a parallel processor is configured with 20 processors, a fairly complicated network can be configured, and the system can be greatly expanded.
Therefore, the present invention not only surpasses the prior art, but also provides an architecture of a parallel processor that operates at high speed by mounting a transputer in the latest FPGA (Field Programmable Gate Array). Another object of the present invention is to provide a parallel processing processor (TPCORE) superior to the performance of a conventional transputer by providing many hardware algorithms for executing a plurality of processes in a single processor.

  The parallel processing architecture of the present invention is a parallel processing architecture of a parallel processing processor that executes a program in an Occam language, and the parallel processor is an initial stage prior to process execution that is sequentially executed in basic units constituting the program. When the process start instruction is executed at the stage, the process is generated. When there is no queue waiting for the process, the generated process is executed and terminated by the process end instruction, or the process is being executed. When channel communication submission, timeout processing or stop command is executed, the system enters an idle state and waits to see the response (response) of the other process's channel. Wait by adding the number to the end of the queue waiting for the process, and wait In the queue waiting for the process, when the process identification number advances and the waiting process becomes the leading process, the leading waiting process is switched, the process is executed, terminated by a termination command, and the initial stage Transition to.

  The parallel processing processor of the present invention is a parallel processing processor that forms a network and executes in the Occam language, an ALU that performs arithmetic operation or logical operation, a microcode ROM that stores microcode that controls the ALU, Holds the register for storing the memory address where the instruction or the instruction to be executed next is stored, the internal register with the general-purpose stack register, and the identification number of the process executed sequentially in the basic unit of the program processed by the processor A processor having a workspace pointer register, a process management register for storing data for managing a standby process, and a microcode ROM controller for controlling the microcode ROM, and connected to the processor to input data. Multiple outputs And the input / output data of the processor or the link, and a workspace is provided, and the identification number for starting the process and the data of the identification number of the next process to be executed are separated by a predetermined address value in the workspace. And a memory that controls the exchange of input / output data of the memory.

  A parallel processing architecture of the present invention and a parallel processing processor using the parallel processing architecture are provided with a process management register, a general-purpose internal register, a memory, and a link block, and a process identification number of a process to be executed and a process number to be executed next are provided. Stored in a process management register and memory, the process identification number is stored in the memory, and formed into a linked scheduling list to execute process switching and channel communication between processes.

The parallel processor (also referred to as TPCORE) of the present invention improves the performance of the transputer by understanding the machine language (assembly language) of the conventional transputer and configuring another processor with a completely different architecture. .
Also, by making the machine language compatible with a conventional transputer, all software previously developed on the transputer can run on this TPCORE, and Occam can also function. Therefore, the development study of the CSP theory using the parallel processor of the present invention can be performed again through Occam.

First, the CPU 10 (central processing unit) which is the main part of the parallel processor of the present invention will be described.
FIG. 1 shows a block configuration of the CPU 10. The CPU 10 includes several types of registers (internal registers), two buses, an ALU ₃₁ (Arithmetic Logic Unit) that performs various arithmetic processes, a control unit that controls TPCORE (50), and the like.
Among the internal registers, Wptr ₁₄ (workspace pointer), Iptr ₁₅ (instruction (instruction) pointer register), Ireg ₂₆ (instruction (instruction) register), Oreg ₂₅ (operand register), general-purpose stack It is composed of Areg ₁₁ , Breg ₁₂ , and Creg ₁₃ of the register.

Iptr ₁₅ is a register having a data width of 32 bits and holding an address where an instruction to be executed next is stored.
Ireg ₂₆ has a data width of 4 bits, and the upper 4 bits of the fetched instruction are stored in this register. The stored value is sent to dedicated hardware for instruction interpretation, where the instruction to be decoded and executed is determined.
Oreg ₂₅ has a data width of 32 bits, and the lower 4 bits of the fetched instruction are stored here, and this stored value is used together with the value of Ireg ₂₆ when interpreting the instruction.
The general-purpose stack registers Areg ₁₁ , Breg ₁₂ , and Creg ₁₃ have a data width of 32 bits and form a stack structure. In accordance with data input and output, PUSH (push) and POP (pop) operations are performed between these registers.

Wptr ₁₄ (workspace pointer) is a register for managing processes, and Fptr ₁₆ (forward pointer) and Bptr ₁₇ (back pointer) are registers for waiting process management.
Wptr ₁₄ stores a 32-bit value (process ID (identification number)) indicating the current process in this register. The lower 2 bits of Wptr ₁₄ indicate the priority of the process. The process ID arbitrarily assigns a 32-bit value called a process ID to each process in order to execute a parallel process with one TPCORE 50.
The process management registers for standby of Fptr ₁₆ and Bptr ₁₇ manage the ID of a process that is not currently executed, that is, the ID of a standby process, while Wptr ₁₄ manages the current process ID. Fptr ₁₆ holds the top process ID of the standby process, and Bptr ₁₇ holds the last process ID. When there are three or more standby processes, they cannot be managed by these two registers, so these are managed by a list structure using the memory ₍₄₂₎ .

Other registers include cnt ₂₁ (counter register) and Temp ₂₉ (temporary register). The cnt ₂₁ has a data width of 32 bits and is used when counting the number of repetitions, the number of shifts, and the number of inputs and outputs. Temp ₂₉ has a data width of 32 bits, and temporarily stores a processing result when ALU ₃₁ cannot execute an operation such as multiplication or division in one clock.

The ALU ₃₁ performs arithmetic and logical operations inside the TPCORE 50. When an operation is required at the time of execution of the processing, the register data and the data arbitrarily generated for the operation are individually sent to perform the operation processing.

Microcode ROM ₂₇ (Microcode ROM) stores microcode, performs communication between registers, communication control between memory ₄₂ and registers, and also controls the function of ALU ₃₁ . It also manages state transitions of other processors. One microcode is 68 bits wide, and the operation of the TPCORE 50 is controlled by each bit. The upper 56 bits of the microcode control the bus, the register, and the ALU ₃₁ , and the lower 11 bits control the operation of the processor.
A microcode ROM controller ₂₄ (Microcode ROM Controller) calculates a microcode address. There are two address calculation mechanisms, which are distinguished by the 64-bit value of the microcode. When this value is “1”, an address is calculated based on the values of Ireg ₂₆ and Oreg ₂₅ , and when “0”, the value of output 9 to 0 bits of the microcode ROM ₂₇ is used as the next address as it is. .

Next, FIG. 2 shows a block diagram of the TPCORE50. In addition to the CPU 10 described above, the TPCORE 50 includes a link block ₄₅ , a memory controller ₄₁ (Memory controller), a memory ₄₂ (Memory _{42-a to 42-d} ), and the like. Each of the memories _{42-a to 42-d} is composed of an 8 Kbyte (kilobyte) block RAM. The link block ₄₅ is composed of four interfaces (links), and communicates or exchanges data with other TPCORE 50.

A memory (Memory ₄₂ ) is provided with an internal memory of 32 KB per one TPCORE 50. This memory ₄₂ is accessed from both the CPU 10 and the link block ₄₅ . These access priorities are managed by a memory controller ₄₁ described later.
The memory ₄₂ can be accessed by two methods, byte access and word access. Since the data width of the write to read and the memory ₄₂ from the memory ₄₂ There are two, memory ₄₂ of 32KByte has a configuration that combines four memories _{42-a (~42-d)} of 8KByte. Each of the memories _{42-a to 42-d} has a data width of 8 bits and a depth of 1024.

The link block ₄₅ includes a link interface, a register, and the like, and four bidirectional serial links (links) are configured in the TPCORE 50, and control of these four links is managed independently of the CPU 10. That is, the link block ₄₅ operates independently of other parts constituting the TPCORE 50. Therefore, when the link block ₄₅ receives data from the CPU 10 or the memory ₄₂ , the link block ₄₅ can transmit and receive data regardless of the operation of the CPU 10.

The memory controller ₄₁ receives a memory access request from the CPU 10 or a memory access request from the link interface. The memory controller ₄₁ adjusts the request according to the specifications of the memory ₄₂ mounted on the FPGA.
The memory controller ₄₁ manages memory access authority and bus data width change (byte width, word width, etc.). Also, the address space can be expanded to 4 GB (Gigabytes) or more.

Next, the memory access authority will be described. The memory controller ₄₁ controls the priority of the memory ₄₂ with one control line. For example, the link block ₄₅ controls the memory ₄₂ when the control signal is “High” level, and the CPU 10 is connected to the memory ₄₂ when the control signal is “Low” level.
When the memory access authority is passed to the link block ₄₅ , the memory ₄₂ is directly connected to the memory ₄₂ on the other TPCORE 50 via the links _{52-a to 52-d,} and enters a so-called DMA (Direct Memory Access) state. For this reason, message passing (message transfer) of the TPCORE 50 is performed at a very high speed because of DMA.

Next, a bus data width change management method by the memory controller ₄₁ will be described.
First, the address bus will be described. Of the memory space (4G) that can be accessed in 32 bits, the TPCORE 50 can access an address space allocated as an internal memory with a faster clock than other address spaces. Since the TPCORE 50 is assumed to be mounted on an FPGA and all the address spaces are regarded as being equal by simplifying the circuit configuration, a 4 GB memory (memory ₄₂ and other memory not shown) is provided. Can be accessed in the same clock cycle.
Further, since the TPCORE 50 is mounted on the FPGA and its capacity is limited, only the lower 15 bits of the 32-bit width are used. Of these 15 bits, 14 to 2 bits are used as an address, and 1 to 0 bits are used as a bank select to determine which of the four memories _{42-a to 42-d} is selected. An example of changing the data width of the address bus is shown in FIG.

Next, the change of the data bus width by the memory controller ₄₁ will be described.
Since the CPU 10 and the links _{52-a to 52-d} can access either 32 _- bit or 8-bit data, a control signal for selecting the data width is output from the microcode ROM ₂₇ in order to control this. For example, when communication is established, the data communicated by the links _{52-a to 52-d} is 8 bits, so the data width is limited to the Byte width.

The word access of the memory ₄₂ will be described. Each of the memories _{42-a to 42-d} can input / output data only at 8 bits. However, by combining the four memories _{42-a to 42-d} , two kinds of data of a word (32 bit) width and a byte width can be output.
FIG. 4 shows the conversion of the data bus data width.
When the TPCORE 50 accesses the memory ₄₂ and the data bus width is determined to be the word width, data is simultaneously output from the four memories _{42-a to 42- d} , and the memory controller ₄₁ causes the four memories _42-a to be output. Data of 32 bits width is formed by combining _{~ 42-d} . At this time, the data output from the address bus uses only the upper 13 bits, and the lower 2-bit memory select portion is not used.

When the data width is designated in byte-wide by the data width control signal describing byte access memory _42, TPCORE50 by using a lower 15bit data byte address bus to the memory _42, stored data memory _{42 a to 42-d} and its address are determined. When the TPCORE 50 performs byte access to the memory ₄₂ , byte _- width data is output from only one memory _{42-a to 42-d} .

  Next, TPCORE 50 has the following (a-1) memory, (a-2) process management register, and (a-3) internal register as preconditions, and the clock is shown in (a-4).

(A-1) The memory ₄₂ will be described.
A memory ₄₂ having a width of 32 bits (one word is 32 bits) is prepared. 1 byte addressing. For example, the direction in which the address increases from address 0x00000000 is the positive direction, and the reverse direction is the negative direction. The amount of memory is not strictly defined here, but may be arbitrary. As memory access, the program proceeds in units of words, but in channel communication, data transfer is performed in units of bytes, so that both words and bytes must be accessible. In order to save various registers when an interrupt occurs, a 5-word area with a 32-bit width is secured at an arbitrary address and fixed as a register saving dedicated area. Cregsaveloc, Bregsaveloc, Aregsaveloc, Iptsaveloc, and Wptraveloc are named for convenience (see FIG. 10) corresponding to the names of the registers for saving them. Also, 4 words of input channel and 4 words of output channel are secured and fixed for external link communication. These are named for convenience as Link ₀ Input,..., Link ₃ Input, Link ₀ Output,..., Link ₃ Output. In the following description, an address (X) means access to an address indicated by X.

(A-2) The process management register will be described.
Five registers of 32-bit width are prepared as process management registers in the processor (CPU 10). Fptr ₁₆ (holding the workspace pointer of the current process) and Fptr ₁₆ and Bptr ₁₇ are prepared as standby process management registers. Two sets of Fptr ₁₆ and Bptr ₁₇ are prepared independently according to the priority. In order to simplify the expression, the suffixes Fptr ₁₆ and Bptr ₁₇ are omitted here, and only the priority symbols are added. For example, Fptr ₀ and Bptr ₀ are used for high priority processes, and Fptr ₁ and Bptr ₁ are used. For low priority processes. Hereinafter, when only Fptr ₁₆ and Bptr ₁₇ are described, it means that the register pair is within the same priority regardless of the priority.

(A-3) The internal register will be described.
As described above, one 32-bit register called an instruction pointer (Iptr ₁₅ ) is prepared. The memory address where the instruction to be executed next is stored is held. Similarly, 32-bit wide general-purpose stack registers Areg ₁₁ , Breg ₁₂ , and Creg ₁₃ are prepared. Optionally, some additional internal registers may need to be provided. Examples of this include cnt ₂₁ (counter register) that holds the number of repeated operations, Temp ₂₉ (temporary register) for temporary data storage, and the following is assumed that cnt ₂₁ is configured (channel) Used for inter-communication).

(A-4) The clock of TPCORE50 will be described.
In the TPCORE 50, two types of clocks are prepared, the clock period used in the high priority process is 1 μ (micro) seconds, and the clock used in the low priority processes is 64 μ seconds.

As described above, the TPCORE 50 having the CPU 10 optimizes hardware such as a process management register, a general-purpose stack register, and a memory (RAM) ₄₂ , and operates in the Occam language, which will be described later. The performance can be further improved.

Next, an outline of the Occam language for controlling the TPCORE 50 will be described.
First, the process processed by the construction will be described. Here, the term “construction” refers to a collection of the most basic primitive (basic) processes such as assignment, output, procedure call (corresponding to a subroutine).
A primitive process is the minimum unit of an assignment statement, input, and output.
The assignment process indicates that a value is assigned to a variable. When a value of y is assigned to a variable x, x: = y is expressed. The input process indicates that a value is input to the variable. When receiving the variable x from ch (channel) 1, ch1? x. The output process indicates that the value is output from the variable. When the variable y is output to ch1, ch1! y.
The declared channel exists between two parallel processes. When a channel is declared, the communicating party does not change during program execution, but the sending side and the receiving side can be switched. Input / output between the TPCORE 50 is performed in synchronization with each other.
For example, when the output process is executed by the upper (front) sequential process, if the lower (rear) sequential process is not executed, the upper process continues to wait until it is executed, and both can communicate Communication starts. In this way, communication is synchronized.

There are six types of construction in the Occam language: SEQ, PAR, ALT, WHILE, IF, and CASE.
The SEQ (sequential) construction is a construction for executing processes in order from the top of the program. The PAR (parallel) construction executes processes in parallel regardless of the order in which they are written. The ALT (orthotropic) construction selects and executes the process that first satisfies the conditions required by the ALT construction. The WHILE construction is repeatedly executed by the process based on a logical type variable attached to the WHILE construction. The IF construction executes the first process in which the guard becomes “true”. The CASE (case) construction selects one process from a plurality of process groups.

Hereinafter, each of the SEQ, PAR, and ALT constructions will be specifically described with reference to a program.
A program example using the SEQ construction is shown below.
SEQ
Process 1
Process 2
・
・
・
Process n

  In the above-described program, the SEQ construction sequentially executes the described processes from Process 1 as Process 2, Process 3,. Then, when the last process Process n ends, the SEQ construction itself ends.

The example of a program using PAR construction is shown.
PAR
Process 1
Process 2
・
・
・
Process n

The PAR construction runs the described process simultaneously. And when all the processes are finished, the PAR construction itself is finished. Processes operating in parallel interact with each other by communicating using a single channel. If one TPCORE 50 is assigned to one process in the PAR construction, the processes in the same PAR construction are started simultaneously. However, the PAR construction executed by one TPCORE 50 is managed in a time division manner and executed in a pseudo-parallel manner. This pseudo parallel operation will be described later.
In addition, priorities can be assigned to processes executed in parallel, and PRI reserved words are added before the PAR construction.

The example of a program using ALT construction is shown.
ALT
input1
Process1
input2
Process2
・
・
・
inputn
Processn

The ALT construction selects one process to be executed from many processes. In the above-described program, input1, input2,..., Inputn indicate input guards, and the processes in the input guards that are in the ready state first are executed. Then, after the selected process is executed, the ALT construction ends.
The ALT construction can also be prioritized in the same way as the PAR construction, adding a PRI reserved word before the ALT. In the Occam language, priorities are given in order from the top, but TPCORE50 and transputer have only two priorities. For this reason, the process described at the top of the program has a high priority, and processes below it have a low priority.

Next, the TPCORE50 network on the FPGA will be described.
As shown in FIG. 5, the TPCORE 50 includes four external interfaces _{52-a to 52-d} (or also referred to as links) as in the conventional transputer. A box ₅₁ indicates the TPCORE 50 main body, and a line orthogonal to the side at the center of each side of the box ₅₁ indicates the interfaces _{52-a to 52-d} .
As shown in FIG. 5, the interfaces _{52-a to 52-d} can be connected to the interfaces _{52-a to 52- d} of other TPCORE 50 to construct a TPCORE 50 network.

6A to 6C are configuration diagrams of the TPCORE network 100. FIG. In the TPCORE network 100, a plurality of TPCOREs 50 are connected via the interfaces _{52-a to 52-d} of the TPCORE 50, and a tree connection (FIG. 6A), a pipeline connection (FIG. 6B), and a lattice connection (FIG. 6 (c)) to construct a network of parallel treatment processors. For example, by using a lattice connection as a graphics accelerator and a tree connection as a parallel database search system, a network can be easily configured in a short time depending on the application form.
In addition, by forming the above-described TPCORE 50 with an FPGA, the topology of the network can be freely modified by a system that applies parallel processing. Therefore, the merit of realizing the TPCORE50 on the FPGA is very large.

Next, the communication operation of the parallel processor using the external link (Link) will be described. Here, for easy understanding, an example of communication using two TPCOREs 50-1 and 50-2 is shown. In FIG. 7, the link interface (link interface) is also simply referred to as a link (Link1, Link2).
As shown in FIG. 7, the communication between the TPCOREs 50-1 and 50-2 is established by an Acknowledge (ACK) packet. If this ACK packet is not sent, the link (link interface) _45a on the transmission (Out) side waits in an idling state until it is received.
For example, when an out instruction is executed in a state where Breg _{12 of} TPCORE 50-1 is 0x80000008, data is to be output to the outside through the Link 2 (link interface) ₄₅ constituting the link block ₄₅ . The CPU 10 passes the contents of the stack registers (Areg ₁₁ , Breg ₁₂ , Creg ₁₃ ) and the process ID to each register of the link interface, and entrusts communication processing to Link 2. Then, the process currently being executed is terminated and the next execution of the scheduling list is started.

After transmitting 1-byte data, the TPCORE 50-1 idles until an ACK packet is sent from the TPCORE 50-2 on the other side, and communication is established when these are received (see FIG. 8). Even after the communication is established, data is transmitted one byte at a time, and data of the number of bytes stored in the cnt 21 is communicated while mutually confirming data transmission / reception with an ACK packet.
Since CPU10 and _{Link1 45a} can not access the memory _42a simultaneously, _{Link1 45a} when this communication is executed to occupy memory _42a. When the communication is completed, the ID passed to Link1 _45a before the communication is added to the tail of the scheduling list formed in the memory _42a . Control to perform this addition is performed by microcode. Simultaneously with the end of communication, the CPU 10 returns from the idling state, _and the occupancy rights of the memories _{42 and 42a} are also passed to the CPU 10. In FIG. 9, TPCORE 50-1 and TPCORE 50-2 stop the processes being executed, pass the authority to use the memory ₄₂ to Link1 _45a and Link2 ₄₅ , and send ACK packets and data between TPCORE 50-1 and TPCORE 50-2. An example is shown.

  Next, parallel processing of a plurality of processes inside a single processor of the TPCORE 50 will be described. The TPCORE 50 has the above-described (a-1) memory, (a-2) process management register, and (a-3) internal register as preconditions.

First, process management of the TPCORE 50 will be described.
In the following, when the register suffix is lowercase, it indicates a register, and the symbol (XX) indicates the data (address value, etc.). For example, Areg ₁₁ indicates a register, and (Areg ₁₁ ) indicates data stored in (or made to) the A register.
The process is managed by Wptr ₁₄ and the scheduling list. Wptr ₁₄ is used to store the ID (identification number) of the current process, and the scheduling list is used to hold a waiting process.
When another process is created or an interrupt occurs while executing a process, the process ID is added as a standby process to the end of the scheduling list. This list is treated as a queue that is stored first and executed first. The scheduling list manages the order of processes executed in the linked list structure.

(B-1) Process ID
A process is a unit of processing, and a process ID (32 bits) is assigned to this process. The lower 2 bits of the process ID indicate the priority of the process, and the priorities are “High” (lower 1 bit = 0) and “Low” (lower 1 bit = 1). The upper 30 bits indicate an address on the work space of the memory ₄₂ stored for each process. The process workspace is managed by the Occam compiler.

(B-2) Work space A memory area called a work space is provided on the memory ₄₂ composed of RAM for each process, and the memory area is a number in units of 32 bit words in the memory negative direction based on the value indicated by the process ID. Prepare a word (always). The work space is used for holding data (various registers), channel communication, execution of an ALT construction instruction, and process scheduling when a process to be processed in parallel is temporarily interrupted by an interrupt of another process. The value of Iptr ₁₅ at the time of starting (or resuming) the process is entered in the first 4 addresses of the workspace (process ID-4, that is, the first word from the workspace).

FIG. 10 shows an example of the work space of the process ID (Wptr ₁₄ ). For example, when accessing the address (Wptr ₁₄ -1) immediately before the address (Wptr ₁₄ ) indicated by the process ID, the value of Wptr ₁₄ is sent to the ALU ₃₁ and the value obtained by subtracting 1 is accessed as the address. Similarly, when accessing the address (Wptr ₁₄ -2), a value obtained by subtracting 2 from the address (Wptr ₁₄ ) is accessed as the address.

(B-3) Work space management The currently executing process ID is held in Wptr ₁₄ . If a new process is created while executing a process, it is added as a standby process to the end of the process scheduling list. This list has a first-in first-out structure (FIFO). The process's unique address (workspace-8) indicated by the process ID, that is, the address (workspace-2 words), stores the work space address (ie, process ID) of the process to be executed next to the process. If there is no process to be executed thereafter, an empty signal (empty, empty flag) is given a value of, for example, 0x80000000 or 0x80000001 (for low priority processes and high priority processes, respectively). By giving the process ID to be executed next to this address (workspace-8), a process scheduling list is formed in the form of a linked list. The first process ID of the standby process is stored in Fptr ₁₆ and the last process ID is stored in Bptr ₁₇ . Address _(Bptr 17 -8) The thus empty is stored. A scheduling list (hereinafter also referred to as a queue) having this structure is held independently for two priorities (high, low). FIG. 10 shows an example of the work space of the process ID (Wptr ₁₄ ) on the memory ₄₂ . Address _{(Wptr 14, Wptr 14 -1,} ···, Wptr 14 -5) and the relationship between the storage location corresponding to the general-purpose register and process management register shown.

Next, specific examples of the work space on the memory ₄₂ are shown in Tables 1 and 2. Table 1 shows the contents of the workspace when executing the PAR construction, and shows the relationship between the workspace relative address and the stored data. Table 2 shows the contents of the workspace when the ALT construction is executed. In any construction, data is stored at an address separated by a predetermined word in the negative direction. In the PAR construction, an address to be executed at the time of starting or returning from a predetermined address, a process ID to be executed next, and a head address of the memory ₄₂ to be accessed at the start of communication are stored. In the ALT construction, the guard selection state, the address executed at the start or return of the process, the ID of the process to be executed next, and the ALT execution state are stored at a predetermined address in the negative direction of the address.

Next, parallel process processing in the single TPCORE 50 will be described.
FIG. 11 shows a process state transition diagram in an environment where several types of processes run in parallel. The parallel processing is a grand stage (initial (basic) stage) before the program is executed. When a startp instruction to start the process is supplied to the TPCORE 50 and the program is executed (ST1), a process is generated (ST2). ). When the queue is empty, the generated process is executed (ST3), and the process is terminated with an endp (end) command. Further, when channel communication is proposed, a time-out process, or a stop command is executed during execution of the process (ST3), the process enters an idling state (ST4) and waits to see the reaction of the channel of the partner process (ST5).
On the other hand, after the process is generated (ST2), when the queue is not empty, the process ID is added to the end of the queue and waits (ST5). While waiting, the process ID advances in the queue. When the waiting process becomes the leading process, the waiting process is changed (switched), the waiting process is executed (ST3), the process is terminated by the endp instruction, and transitions to the first ground stage ( ST1). Thereafter, the same transition is repeated.

Hereinafter, a specific example of the processing of the parallel process described above will be described.
If there is a construction that creates a new process, such as a PAR construction or an ALT construction, in the program created in the Occam language, the compiler creates an assembler code group to perform the following execution.
(A1) Create a process ID to be generated.
(A2) A process is generated using the assembler instruction startp.
(A3) The generated process is added to the scheduling list according to its priority.
The execution of (a1) to (a3) is repeated by the number of processes to be generated (the number of parallel processes).

Next, process execution and switching will be described with reference to FIGS.
TPCORE 50 executes the process indicated by the value of Wptr ₁₄ . However, process switching occurs when a process being executed is not executable or the processor (TPCORE 50) is in an idling state. In other words, when the idling state is entered, the idling state is reduced by executing another process rather than waiting for the state to become executable again.
There are the following examples of the above-mentioned factors that make the process unexecutable or idling.
(B1) An assembler instruction that terminates or stops the process is executed.
(B2) When a communication partner is not ready when an input / output command is executed.
(B3) When a target time is not elapsed when an instruction for delay or timeout processing is executed.
At this time, the hardware mechanism in the TPCORE 50 is as follows.
(B4) The presence or absence of a standby process is checked. If there is no standby process, the system is set to an idling state.
(B5) The value of Fptr ₁₆ is stored in Wptr ₁₄ . At the same time, the value stored in the address (Wptr ₁₄ −1) is stored in Iptr ₁₅ .
(B6) Next, the ID of the standby process is extracted from the address (Wptr ₁₄ -2), and stored in Fptr ₁₆ .
(B7) The process stored in Wptr ₁₄ is started.
The transition of the hardware state for performing such process switching is described in microcode and controlled by it. In addition, there is an interrupt as a factor that causes the process to switch exceptionally, which will be described later.

Next, the scheduling list described above will be described.
The scheduling list is formed on the memory ₄₂ and manages the order of processes executed in the linked list structure. A process has its own workspace, which is used to form a scheduling list. FIG. 12 shows an example of a scheduling list when there are four processes. In order to avoid complication in FIG. 12, the symbol Wptr ₁₄ is abbreviated as Wptr, and the process number is appended to Wptr.
In the scheduling list formed on the memory ₄₂ (Memory), for example, when the ID of a certain process (process 0) is an address (Wptr ₀ ), the process ID executed next to that process is the address (Wptr ₀ − 2). Further, the instruction acquisition destination address (value of Iptr ₁₅ ) when the process of its own begins to be executed is stored in (Wptr ₁ −1). The fourth last process ID (address (Bptr ₁₇ )) is stored in the address (Wptr ₃ ). As shown in FIG. 12, for example, a link list structure in which Wptr ₃ of the next (fourth) process ID is stored in the address (Wptr ₂ -2) related to the third process, and the process itself points to the next process. The process is waiting in the order of execution.
The TPCORE 50 prepares two types of registers, Fptr ₁₆ and Bptr ₁₇ , in order to access such a scheduling list.
The first process ID of the standby process is stored as Fptr ₁₆ , and the last process ID is stored as Bptr ₁₇ . When the process being executed is terminated and the next standby process is started, the Fptr ₁₆ is accessed to start the next process. Further, when a process is generated, the last part of the scheduling list is accessed using Bptr ₁₇ and this process is added. The operation mechanism of the scheduling list and the control of Fptr ₁₆ and Bptr ₁₇ are controlled by microcode.

The scheduling list is composed of three elements: an address (Fptr ₁₆ ), an address (Bptr ₁₇ ), and a memory (intermediate process), and a standby process is linked in a linked list structure.
Therefore, since the waiting process is held in the memory ₄₂ , the number of registers used is reduced, and hardware resources can be saved. If a standby process is held by a register or the like, when a standby process larger than the register prepared as the scheduling list is generated, the generation of the process must be prohibited until the register becomes empty. This complicates the hardware structure. However, with the linked list structure described above, standby processes can be generated almost infinitely, and the hardware structure can be simplified.

Next, execution of the PAR construction in the TPCORE 50 will be specifically described.
(C-1) Process Execution The processor 50 executes a process based on Iptr ₁₅ and updates each value of the workspace indicated by Wptr ₁₄ for each machine instruction execution (if necessary).
(C-2) Process Start The process ID of the process to be started is entered in Areg ₁₁ , and the address of the instruction to be executed at the start of the process and the offset (Iptr ₁₅ ) are entered in Breg ₁₂ (Occam compiler) ). If there is no waiting process (when the process ID is not registered in the scheduling list; address (Fptr ₁₆ ) = (Bptr ₁₇ ) = empty), the data of Areg ₁₁ is stored in Bptr ₁₇ and the address (workspace-4) Iptr ₁₅ + 4 + Breg ₁₂ is stored. If there is a waiting process, that is, if address (Fptr ₁₆ ) ≠ address (Bptr ₁₇ ), data of Areg ₁₁ is stored at address (Bptr ₁₇ −8).

(C-3) Interruption / termination of execution of the current process When the current process executes a process termination or stop command, executes an I / O command, or waits, delays, or timeouts in channel communication When the execution of the instruction to be executed is started, the process is interrupted (see ST11a in FIG. 13, ST21 in FIG. 14, ST11b in FIG. 15, ST31 in FIG. 16).

(C-4) Process Switching The process switching operation in the PAR construction will be described (see FIGS. 13 to 16 and Tables 3 to 6). In Tables 3 to 6 and Table 8, the suffix of each pointer register is omitted to avoid complexity.
The presence or absence of a waiting process is checked. If there is no waiting process, the processor (TPCORE 50) itself enters an idling state (see FIG. 16, Table 3).

待機プロセスが１個以上ある場合（Ｆｐｔｒ_１６≠Ｂｐｔｒ_１７）プロセスを切り替えるためにＦｐｔｒ_１６の値をＷｐｔｒ_１４に格納し、アドレス（Ｆｐｔｒ_１６−４）にある値をＩｐｔｒ_１５に格納し、アドレス（Ｆｐｔｒ_１６−８）に保持されている次のプロセスのプロセスＩＤをＦｐｔｒ_１６に格納するという手続きを踏みプロセスの切り替えを行う（図１３と表４のＴａ１，Ｔａ２、図１５と表５のＴＣ１，ＴＣ２参照）。

When there are one or more waiting processes (Fptr ₁₆ ≠ Bptr ₁₇ ), the value of Fptr ₁₆ is stored in Wptr ₁₄ in order to switch processes, the value in the address (Fptr ₁₆ -4) is stored in Iptr ₁₅ , and the address ( fptr ₁₆ -8 process ID of the next process, which is held) to switch the process down the procedure of storing the fptr ₁₆ (Ta1 in FIG. 13 and Table 4, Ta2, TC1 of Figure 15 and Table 5, See TC2).

なお待機プロセスが１個のみの場合（Ｆｐｔｒ_１６＝Ｂｐｔｒ_１７）、プロセスを切り替えた後、次のプロセスのプロセスＩＤの代わりにＦｐｔｒ_１６にｅｍｐｔｙを入れておく。なおプロセスを切り替えようとしてＦｐｔｒ_１６＝Ｂｐｔｒ_１７＝ｅｍｐｔｙであった場合、Ｗｐｔｒ_１４＝ｅｍｐｔｙとしてプロセッサ（ＴＰＣＯＲＥ５０）はアイドリング状態となる。高優先度のプロセスから復帰して低優先度のプロセスに切り替わる場合、たとえアドレス（Ｆｐｔｒ_１６）＝（Ｂｐｔｒ_１７）＝ｅｍｐｔｙと待機プロセスがなくてもワークスペース割り込み保存領域のＷｐｔｒｓａｖｅｌｏｃにあるアドレス（Ｗｐｔｒ_１４）を持ってきて実行を再開させる（図１３と表４のＴａ３、図１５と表５のＴＣ３参照）。そして後述の「割り込みからの復帰」と同じ操作が行われる。
また、高優先度キューが空で中断プロセスは高優先度の場合、待機プロセスが有るとＷｓａｖｅｌｏｃをＷｐｔｒ_１４に格納し、アドレス（Ｗｐｔｒ_１４−４）のデータをＩｐｔｒ_１５に格納し、待機プロセスを取り出し、実行する（図１４と表６参照）。

If there is only one standby process (Fptr ₁₆ = Bptr ₁₇ ), after switching the process, empty is entered in Fptr ₁₆ instead of the process ID of the next process. If Fptr ₁₆ = Bptr ₁₇ = empty in an attempt to switch processes, Wptr ₁₄ = empty and the processor (TPCORE50) enters an idling state. When returning from a high-priority process and switching to a low-priority process, even if address (Fptr ₁₆ ) = (Bptr ₁₇ ) = empty and there is no waiting process, the address (Wptr) in the Wptsaveloc of the workspace interrupt storage area ₁₄ ) and resume execution (see Ta3 in FIG. 13 and Table 4, TC3 in FIG. 15 and Table 5). Then, the same operation as “return from interruption” described later is performed.
Also, if the high priority queue is interrupted process empty high priority, stores Wsaveloc the waiting process is in the Wptr _14, stores the data of the address _(Wptr 14 -4) in iptr _15, the waiting process Take out and execute (see FIG. 14 and Table 6).

(C-5) High-priority process switching during low-priority process execution High-priority process (Fptr _{(16) 0} = Bptr _{(17) 0} ) during low-priority process execution Is generated, or when returning from the idling state and Fptr _{(16) 0} = Bptr _{(17) 0} ≠ empty, execution of the high-priority process in which only that process is in Queue is interrupted. In this case, Wptr ₁₄ , Iptr _{15 of} the currently executing process, and Areg ₁₁ , Breg ₁₂ , and Creg ₁₃ of the stack register are stored in a predetermined storage area of the workspace (Wptraveloc, Iptsaveveloc, Aregsaveveloc, Bregsaveveloc, Bregsavec To Wptrsaveloc + 16). Then _(fptr 16 Process 0) fptr ₀ to Wptr _14, it stores the contents of the address (Fptr ₀ -4) to iptr _15.

(C-6) Return from interrupt If the scheduling list of the high priority process is empty and the work space address before the interrupt is stored in Wptsaveloc, the interrupt is returned. Wptr ₁₄ , Iptr ₁₅ , Areg ₁₁ , Breg ₁₂ , and Creg ₁₃ are returned from the save destination memory ₄₂ to the register. Then, Wptrsaveloc = empty is stored.

Next, communication between channels in the TPCORE 50 will be described.
In the TPCORE 50, when a communication assembly instruction such as “in” or “out” is executed, it is first checked whether the communication communicates with a process in the same TPCORE 50 or with another TPCORE 50. In the case of communication using an external link (Link), the current values of Areg ₁₁ , Breg ₁₂ , Creg ₁₃ , and Wptr ₁₄ are passed to the link interface, and all rights of communication processing are left to the link interface. In the case of internal communication, the channel on the memory ₄₂ is accessed, the ID stored therein is read, and the subsequent execution is performed. After confirming the internal communication, the TPCORE 50 does not immediately perform the input / output operation, but checks whether or not this communication channel is already enabled by an ALT related assembler instruction. If the channel is not an ALT construction channel, input / output processing is started.

Hereinafter, execution of internal communication in the TPCORE 50 will be specifically described.
(D-1) Channel One word is secured in an arbitrary area in the memory to be used for communication between processes (prepared by the Occam compiler). This address is a channel address. The channel address stores a process ID or, for example, empty (0x8000000x; X = 0, 1 indicates priority) as an initial value.
(D-2) Start of inter-channel communication When inter-channel communication is requested, the Occam compiler stores the number of data transmitted / received to / from Areg ₁₁ as information necessary for communication, the channel address in Breg ₁₂ and the data transmitted / received to Creg ₁₃ Stores the address of the memory area. When communication is started, first, it is checked whether or not this channel is used by the ALT construction. Otherwise, input / output between channels is started between the two processes running in parallel.

(D-3) Proposal of communication In the above-described pseudo-parallel operation, processes are executed in parallel, but only one instruction (TPCORE50) can execute only one instruction at a time. Only one is executed. Therefore, the channel communication eventually takes the form of data exchange between the preceding process and the subsequent process.
In the preceding process, when predetermined data is stored in the stack registers Areg ₁₁ , Breg ₁₂ , and Creg ₁₃ and the execution unit of the instruction corresponding to the inter-channel communication is reached, if the memory indicated by the channel address is empty (empty), workspace (address (Wptr ₁₄₎ with indicated are) from one word negative addresses _(Wptr 14 -4) to store the address of the instruction to be started immediately after inter-channel communication, two more words negative addresses (Wptr ₁₄₎ The value of Creg ₁₃ is stored in -12 (ie, data storage destination address). The current process ID is stored in the channel address. Then, this process is removed from the scheduling list, and the next waiting process is executed. That is, the data of Fptr ₁₆ is put in Wptr ₁₄ and the address (Fptr ₁₆ -4) is set to Iptr ₁₅ . As a result, the process enters an idling state by waiting for input / output. When there is no standby (later) process, the processor (TPCORE50) enters an idling state.

(D-4) Communication establishment When the process is switched and the execution of the subsequent process is started and the command unit corresponding to the start of the communication is reached, the algorithm described in the above communication is executed. However, since the corresponding channel address (indicated by the address (Breg ₁₂ )) has already been written with non-empty information (that is, the process ID of the preceding process) in the above-described operation, communication with that process is established. Become. At this point, check whether the queue waiting for the process is empty.
If not empty, Fptr ₁₆ ≠ empty, it places the process ID of the other party address _(Breg 12 -8) this means that running in parallel other processes other than the communication party processes (which is effective) Put the process at the end of the queue.
If the queue is empty Fptr ₁₆ = empty, the partner process ID is stored in Bptr ₁₇ . From the process ID of the other party, the head address of the other party's work space is known, and from that point, the address where data should be held (or held) in the other party's channel communication is stored at the address -12. This is the data that is stored in the address _(Breg 12 -12) say plainly. By this operation, the data holding address of the preceding address and the data holding address of the own (later) process (stored in the Creg ₁₃ as described above) are clarified. The preceding process whose process ID is written in the channel address does not remember whether this communication is input or output for itself at this point, but the subsequent process has this information (examine the current command and input or output the channel). Therefore, it is possible to input / output between channels without problems (that is, it is possible to unambiguously determine which is the source and which is the destination). At this time, the data corresponding to the value of Areg ₁₁ (number of communication bytes) is moved from the transmission side to the reception side. Since Areg ₁₁ is often used for other purposes, the value is copied to cnt ₂₁ of an optional (counter) register at the start of communication in order to store the number of transfer bytes.

(D-5) Termination of communication As described in “Proposal of communication”, the preceding process in the idling state is added to the end of the scheduling list. Bptr ₁₇ = address (Breg ₁₂ ) and address (Bptr ₁₇ -4) store the address of the instruction to be executed first after the preceding process returns. Then, the corresponding channel address is set to empty.

FIG. 17 and Table 7 show state transition diagrams of communication between the two processes.
The two processes are a process A (preceding process) and a process B (subsequent process). First, the process A is executed (ST51). At this time, the process B is on standby (ST54). When a channel communication command is executed in the process A, the number of movement data, the channel address, and the data storage destination address are stored in the stack registers (Areg ₁₁ , Breg ₁₂ , Creg ₁₃ ), and channel communication is started (ST 52). The ID of process A is stored in the channel address, process A is removed from the queue, process switching processing is performed, and process A is set to the idling state (ST53). When the process A is switched to the process B, the process B starts executing the process, and when there is a channel communication command, executes the channel communication (ST56). The data of the channel address is stored in the process ID of the counterpart, and the process A communication information such as the data source address and the number of data is accessed. Then, data movement between process B and process A is performed (ST57), while process B ends its operation (ST58). Then, the process A returns to the waiting list and waits for the queue (ST59). When the ID of process A comes to the top, process A resumes (ST60), interrupted processing is performed, and process A ends with a process end command (ST61).

Next, ALT construction will be described.
An ALT construction consists of two or more isomorphic structures. This structural unit is a logical expression called guard and a channel input, or a part composed of only channel input and a process following it (guard + process).
Suppose that some of the other processes running in parallel try to communicate with any of the channels that constitute the guard of the ALT instruction process. The ALT instruction is a mechanism that selectively executes the process following the first guard (which is a logical expression is satisfied) and a channel input (this process is referred to as the guard being removed). This mechanism is one of the important programming methods of CSP theory.

Next, execution of ALT construction on the TPCORE 50 will be described with reference to FIG. 18 and Table 8.
(E-1) Internal State of ALT Construction The ALT construction is realized by transitioning between three states of “Enable”, “Wait”, and “Ready” and a Reset state. . These states are distinguished by a 32-bit width value, and the value is held in a specific memory area (in the workspace of an ALT process described later) when the ALT construction is executed. For example, these values are 0x80000001, 0x80000002, and 0x80000003, respectively.

(E-2) ALT Construction Process FIG. 18 and Table 8 show state transition diagrams of the ALT construction. Starting an ALT construction indicates that one independent process is started. The memory ₄₂ has its own work space, and the value of the head address is set as the process ID. The value is stored in Bptr ₁₇ . Then add 0x80000001 representing the state "enable" in the negative direction third word addresses _(Wptr 14 -12 from the address (ST81, see F1).

（ｅ−３）ガード入力の有無の検査
すべてのガードについて、ガードごとに以下のことを行う。ガードの一部に論理式を使っている場合、ＯｃｃａｍコンパイラはＡＬＴコンストラクション実行時での論理式の結果値をＡｒｅｇ_１１に入れるようにする。
ガードの論理式実行においてＡｒｅｇ_１１が真値をもっていれば、次にチャンネル入力のチャンネルアドレスの値（Ｂｒｅｇ_１２に格納されている）を検査する（図１８，Ｆ２参照）。ここ（Ｂｒｅｇ_１２）がｅｍｐｔｙでなくすでに他のプロセスＩＤが書き込まれていたら（即ちチャンネル出力プロセス側からのチャンネル通信の提起が始まっていることを示す）、ＡＬＴプロセスは「レディ」状態となり（ＳＴ８３，Ｆ４参照）、Ｗｐｔｒ_１４にレディフラッグを示す0x80000003を格納すると同時にアドレス（Ｗｐｔｒ_１４）に分岐先未決定フラグ（１）を格納する。
この時点でプロセススケジューリングリストにプロセスが存在する場合、リスト先頭で待っているプロセスのワークスペースポインタ（Ｆｐｔｒ_１６）をアドレス（チャンネルアドレス−８）に格納させ、Ｆｐｔｒ_１６＝アドレス（チャンネルアドレス）としてＡＬＴコンストラクションプロセスと通信するプロセスをリスト先頭に持ってくる（すでにそうなっていればこの部分はスキップ）。
あるいはスケジューリングリストが空であればＢｐｔｒ_１７にチャネルアドレスを格納するガードのチャンネルが未入力の場合（Ａｒｅｇ_１１の値が偽値であるか、アドレス（Ｂｒｅｇ_１２）がＡＬＴコンストラクションプロセスのＷｐｔｒ_１４値であるか）このガードは無視される。ガードの論理式が真でかつアドレス（Ｂｒｅｇ_１２）＝ｅｍｐｔｙであればアドレス（Ｂｒｅｇ_１２）にＡＬＴコンストラクションプロセスのワークスペースアドレス（Ｗｐｔｒ_１４に保持されている）を入れる。（ガード有無の検査については、図１８，表８を参照。）

(E-3) Inspection of presence or absence of guard input For all guards, the following is performed for each guard. When a logical expression is used as a part of the guard, the Occam compiler puts the result value of the logical expression at the time of executing the ALT construction into Areg ₁₁ .
If Areg ₁₁ has a true value in the execution of the guard logical expression, the value of the channel address of the channel input (stored in Breg ₁₂ ) is checked (see FIG. 18, F2). If (Breg ₁₂ ) is not empty and another process ID has already been written (that is, the channel output process side has started to propose channel communication), the ALT process enters the “ready” state (ST83). see F4), stores simultaneously storing 0x80000003 indicating the ready flag to Wptr ₁₄ address (branch destination pending flag Wptr ₁₄₎ (1).
If there is a process in the process scheduling list at this point, the work space pointer (Fptr ₁₆ ) of the process waiting at the top of the list is stored in the address (channel address-8), and ALT is set as Fptr ₁₆ = address (channel address). Brings the process that communicates with the construction process to the top of the list (if this is the case, skip this part).
Alternatively, if the scheduling list is empty, the guard channel for storing the channel address in Bptr ₁₇ is not input (the value of Areg ₁₁ is a false value, or the address (Breg ₁₂ ) is the Wptr ₁₄ value of the ALT construction process. Is this) This guard is ignored. If the logical expression of the guard is true and the address (Breg ₁₂ ) = empty, the work space address of the ALT construction process (held in Wptr ₁₄ ) is entered in the address (Breg ₁₂ ). (Refer to Fig. 18 and Table 8 for the inspection for the presence or absence of guards.)

(E-4) Standby state (Wait)
After waiting for input all of the channel (ie When the workspace address of ALT process is written in the channel address of the channel being used to guard), address (Wptr 14 _-12) is stored in the 0x80000002 indicating "standby" Then, the next waiting process is activated with Wptr ₁₄ = Fptr ₁₆ (Fptr ₁₆ -4 is stored in Iptr ₁₅ ) (see ST82 and F3).
Thus again the ALT construction process is removed from the scheduling list. The ALT construction process waits for the input of the channels that make up the guard.
The branch destination undetermined flag (1) is stored in the head address (Wptr ₁₄ ) of the workspace. As described above, if a channel communication request is already detected during the check for the presence of a guard input, the state transitions to the next ready state without passing through this state.

(E-5) Ready state (Ready)
If the logical expression (if any) that constitutes one of the guards has a true value and an input is input to the channel, the workspace is stored in Fptr ₁₆ and the ALT construction process is the first waiting process in the schedule list. . In Areg ₁₁ , a value 0x80000003 indicating “ready state” is entered. A process attempting to access a channel to the ALT construction process obtains the ALT process workspace from the channel address and examines the value stored therein. If this value is 1, it is determined that this channel address is being used by the ALT process (refer to the description of the usage check method in the ALT construction in the above-mentioned "start of inter-channel communication"). This ALT construction process is registered again at the head (Fptr ₁₆ ) of the scheduling list by the channel output side process (see ST83 and F6).

(E-6) Guard reset (Reset)
In the input guard of the ALT construction process, the logical expression is satisfied and channel access is only allowed at the first time when the guard is removed. All other guards must be reset. During the ALT construction process, the value of Areg ₁₁ is the result of the guard formula.
If channel communication is made from another process but the logical expression is not true, Areg ₁₁ is reset to a false value. When the logical expression is true but the channel communication is not performed, “empty” is stored in the address (channel address) of the channel. The channel whose input guard is removed checks the contents of the address (Wptr ₁₄ ) (holding the workspace of the ALT construction process) and checks whether it is still -1. If it is -1, it means that the destination has not been determined, so the process ID of the other party is stored as address (Wptr ₁₄ ) = address (channel address). Then, the address of the process after the removal of the guard is stored in Iptr ₁₅ and the execution is transferred there (see ST84, F7).

In the above, the implementation method of PAR and ALT construction, the hardware algorithm about the multiple processes and channel communication method in one microprocessor (processor) were described.
As described above, the TPCORE 50 of the present invention can execute a plurality of processes only within one processor. This is because the hardware algorithm has been devised and implemented so that the parallel processing command (constructor) of Occam can be executed inside the single unit.
That is,
-Sequential execution (sequential execution of normal single instructions) (SEQ construction)
・ Parallel processing (PAR construction)
・ Inter-process data communication and synchronization (channel concept)
・ Multi-channel input processing (ALT construction)
By devising.

  Although it has been shown that the TPCORE 50 mounted on the FPGA of the present invention can completely execute the instructions of the transputer, it is completely different from the conventional architecture. As a result, differences in the memory access method, such as (a) access rate and TPCORE operating frequency of the memory and external interface, and (b) homogenization of the memory address space, have led to improved performance.

  In the present invention, Occam is a language created based on the CSP theory. The program of the present invention shows an assembly of several processes. The ground stage of the present invention indicates a basic stage before a start instruction is executed in the transition state of a process in parallel processing. The process of the present invention shows the actual situation of executing a certain action sequentially. The construction is a collection of the most basic primitive processes such as assignment, output, and procedure call (corresponding to a subroutine). A channel is a concept or means used for communication (data exchange) between processes running in parallel. The queue of the present invention represents a queue or scheduling list. The workspace of the present invention indicates a memory space for storing constructions, instructions, identification numbers, addresses, data, and the like. The scheduling list of the present invention is a list formed by storing the identification numbers of execution processes and standby processes in a memory. The idling of the present invention indicates a standby state before the processor executes the program.

  As described above, the parallel processor of the present invention is a compact processor that reduces the number of gates and logic cells of the main unit as much as possible by reducing the number of gates and logic cells as much as possible by refining and designing the conventional transputer architecture. It was realized. As a result, a maximum of 18 TPCOREs can be incorporated into one FPGA with the largest FPGA currently available. Under this condition, a four-stage tree structure in which a maximum of eight TPCOREs are arranged in the root portion, or a 4 × 4 mesh in a lattice form can be incorporated into one FPGA.

  In addition, since the TPCORE of the present invention is formed by FPGA, when the network is configured, the topology can be freely modified by a system to which parallel processing is applied. Therefore, the merit of realizing TPCORE on FPGA becomes very large.

Furthermore, the system architecture of the TPCORE of the present invention is synchronized with the operating frequency of the TPCORE, unlike the conventional transputer, in terms of the data transfer rate to the external interface and the memory access rate. In TPCORE, the interface transfer rate and clock are independent.
Further, the transputer memory has a hierarchical internal memory and a fast access memory, but in the TPCORE of the present invention, all the memories are homogenized and the access rate is the same in all 4 Gbyte spaces. That is, all memory spaces can be accessed uniformly at the same clock rate.

It is a block diagram of CPU of this invention. It is a block diagram of a parallel processing processor. It is a conversion diagram of the data width of the address bus. It is a conversion figure of the data width of a data bus. It is a block diagram of the parallel processing processor which has an interface. It is a block diagram of a TPCORE network. It is a figure which shows the operation | movement of the communication start of TPCORE. It is a figure which shows the operation | movement when communication of TPCORE is materialized. It is a figure which shows the communication operation of TPCORE. It is a figure which shows the work space of process ID. It is a figure showing the state transition of 1 process in parallel processing. It is a figure which shows the structure of a scheduling list. It is a process switching state transition diagram showing the operation of PAR construction. It is another process switching state transition diagram showing the operation of PAR construction. It is another process switching state transition diagram showing the operation of PAR construction. It is another process switching state transition diagram showing the operation of PAR construction. It is a state transition diagram which shows operation | movement of the channel communication between processes. It is a state transition diagram showing the operation of ALT construction.

Explanation of symbols

10 ... CPU, 11 ... Areg (A register), 12 ... Breg, 13 ... Creg, 14 ... Wptr (workspace pointer), 15 ... Iptr, 16 ... Fptr, 17 ... Bptr, 21 ... cnt, 22 ... clk, 23 ... Timeout, 24 ... Microcode ROM controller, 25 ... Oreg, 26 ... Ireg, 27 ... Microcode ROM, 28 ... Microcontroller, 29 ... Temp, 31 ... ALU, 41 ... Memory controller, 42, 42-a to 42- d ... Memory, 45 ... Link block, 50, 50-1, 50-2 ... TPCORE, 52-a to 52-d ... Link (Link) interface, 100 ... TPCORE network.

Claims (20)

A parallel processing architecture of a parallel processor that executes a program in an Occam language, wherein the parallel processor is a start instruction of the process at an initial stage before execution of a process that is sequentially executed in a basic unit constituting the program Is executed, and when there is no queue waiting for the process, the generated process is executed and terminated with an end command of the process, or channel communication is raised or timed out during the execution of the process. When a process or stop command is executed, the system enters an idle state and waits to see the response of the other party's channel. When the process is created and there is no process waiting, the process identification number is placed at the end of the process waiting queue. Add and wait, while waiting for the above process in the queue waiting for the process Parallel processing architectures scan identification number advances, the waiting process is switched processes at the top stand becomes the head process the process is executed to exit the end command, the process proceeds to the initial stages. The parallel processor has a pointer register and a memory. When executing the process, the parallel processor stores an identification number of the process in the pointer register or a workspace of the memory, and the process stored in the workspace is identified by the identification number. A plurality of processes are linked in a linked structure, and the process indicated by the value of the workspace is executed according to the identification number. When the executing process is not executable or the processor is in an idling state, the process is executed. The parallel processing architecture according to claim 1. The parallel processor, when executing parallel construction of the process, exchanges the identification number between the pointer register and the workspace, detects a queue of the workspace, and executes a head process of the queue. The parallel processing architecture described. When the parallel processor performs channel communication between the processes, the process identification number is stored in the workspace of the memory, and the process is switched from the queue of the workspace. The parallel processing architecture according to claim 2. When the parallel processor executes the alternative construction of the process, it sends and receives the identification number in the pointer register and the workspace, detects the guard value of the process, and detects the first process in which the guard is removed. The parallel processing architecture according to claim 2, wherein the processing is executed. A parallel processor that forms a network and executes in the Occam language,
An internal unit having an ALU that performs arithmetic or logical operations, a microcode ROM that stores microcode that controls the ALU, a register that stores a memory address in which an instruction or an instruction to be executed next is stored, and a general-purpose stack register A register, a workspace pointer register that holds an identification number of a process that is sequentially executed in a basic unit of a program processed by the processor, a process management register that stores data for managing a standby process, and A processor having a microcode ROM controller for controlling the microcode ROM;
A plurality of links connected to the processor for inputting and outputting data;
The input / output data of the processor or the link is stored and a work space is provided, and the data of the identification number for starting the process and the identification number of the next process to be executed are stored in the work space apart by a predetermined address value. A memory that forms a scheduling list to which the identification numbers are concatenated;
A parallel processing processor comprising: a memory controller that controls transmission / reception of input / output data of the memory. 7. The parallel processing according to claim 6, wherein the process is managed by the workspace pointer register and the scheduling list, the workspace pointer register stores an identification number of a current process, and a standby process is held in the scheduling list. Processor. The parallel processing processor according to claim 6, wherein a process indicated by the value of the workspace pointer register is executed, and the executing process is switched when the executing process cannot be executed or when the processor is in an idling state. . 9. The parallel processing processor according to claim 8, wherein when another process is created or an interrupt occurs while executing the process, the identification number of the process is added to the end of the scheduling list as a waiting process. The memory is formed on the same substrate as the processor on the FPGA, and the work space is provided with a memory area on the memory for each process, and a memory address of the memory area is set based on the value indicated by the process identification number in the memory area. The parallel processing processor according to claim 6, wherein several words are provided in a predetermined direction in a negative direction. The parallel processing according to claim 6, wherein the work space is used for data holding of each register, channel communication, execution of an alternative construction or process scheduling when the process to be processed in parallel is temporarily interrupted by an interrupt of another process. Processing processor. The process management register has first and second pointer registers, the scheduling list is formed by the first process, the last process, and an intermediate process, and the first pointer register holds the identification number of the first process. 7. The parallel processor according to claim 6, wherein the second pointer register holds an identification number of the last process, forms a linked list structure with the identification number, and connects the standby processes. The internal register has first and second stack registers, stores the process identification number of the instruction of the parallel construction to be started when executing the parallel construction in the first stack register, and is executed at the start of the process The address and offset are stored in the second stack register. When there is a waiting process, the data of the first stack register is stored at the memory address indicated by the first pointer register. The data of the first stack register is stored in the second pointer register, and the third pointer register for storing the instruction pointer and the data of the second stack register are stored at a predetermined address of the memory. Parallel processor. When executing the parallel construction, the processor checks whether there is a standby process, and when there is the standby process, exchanges data between the third pointer register and the first pointer register to switch the process. The parallel processing processor according to claim 13, wherein the idling state is set when there is no data. When an interrupt occurs during execution of the process, the processor stores the data of the workspace pointer register, the instruction pointer register, and the internal register in a predetermined area of the workspace, and the workspace pointer register and the instruction The parallel processing processor according to claim 6, wherein data of the first pointer register is stored in the pointer register. When the inter-channel communication command is executed, the preceding process stores the command address started immediately after channel communication and the data in the internal register in the workspace if the channel address value is empty. The parallel processing processor according to claim 6, wherein the process is removed from the scheduling list and the next waiting process is executed. The processor stores the process identification number of the communication partner in the second pointer register when there is a queue waiting for the process as a result of checking the queue state waiting for the process after the channel communication between the processes is established. The parallel processing processor according to claim 16, wherein an identification number is added to the end of the queue waiting for the process, and when there is no queue waiting for the process, the second pointer register stores the process identification number of the communication partner. The ortho-constructive construction of the process is composed of a logical expression constituting a guard and a part and a process composed of only channel inputs or channel inputs, and the result of the logical expression of the guard is a true value and the first for process management. When the process is in a ready state and there is a process in the scheduling list, the first stack register stores a work space pointer of the process waiting at the head of the list, and the process of the ortho construction 7. The parallel processing according to claim 6, wherein when the process that communicates with the process is positioned at the top of the list and there is no data in the scheduling list, the second pointer register stores the value of the second stack register for the process management. Processor. After the above-described alternative construction waits for input of all the channels, a value indicating a standby state is stored in the workspace of the memory, and a value of the first pointer register is stored in the workspace pointer register. The parallel processing processor according to claim 18, wherein the parallel processing processor is started. In the ortho construction, when input data is supplied to the channel when a logical expression constituting the guard is true, the data of the workspace is stored in the first pointer register and the process of the ortho construction is performed. The parallel processing processor according to claim 18, wherein a value indicating a ready state is stored in the first stack register as a first waiting process of scheduling.

Images