Network structure for parallel software processing

A network for parallel processing for high performance parallel processing systems. Such a network solves the network communication problem by making use, in its nodes, of large size memory units capable of being simultaneously accessed by several processing units installed on the network edges intersecting that node. The processing units provide a large number of high performance virtual processors performing processing operations on both the two memories between which the processing unit is connected and transfer operations therebetween.

CROSS REFERENCE TO RELATED APPLICATIONS 
This application is a national phase of PCT/RO 92 00005 files 12 Mar. 1992 
and based, in turn, on Romania national application 148526 filed 10 Oct. 
1991 under the International Convention. 
1. Field of the Invention 
The invention relates to a network for parallel processing of logic 
programs intended to provide a highly parallel processing system to be 
used in fields in which data processing performances should be very high. 
2. Background of the Invention 
High performances in data processing have been obtained with parallel 
processing whereby the processing processes are decomposed into components 
distributed among concurrently operating equipement. Among the well-known 
parallel processing structures are: the pipeline architecture and 
multiprocessor architecture (Bell,C. G., Newell, A.--Computer structures: 
reading and exemples, McGraw-Hill Book Comp., New York, 1971; Treleaven, 
P., Vanneski, M.--Future parallel computers, Springer Verlag, Berlin, 
1987). 
The pipelining procedure is an approach to parallel processing at the 
instructions bit level: Instruction are analyzed and decomposed into 
constituent operations and then each of the operations is executed on 
dedicated serially connected units. The output of a preceeding unit s 
taken over by the subsequent unit which, after having executed the 
appropriate operations, transfers the output to the next unit. (Chen, T. 
C.--Parallelism, pipelining and computer efficiency, Computer Design, 
January 1971). 
Well-known systems have benefitted from such a structure for increasing 
their performances (Flores, I.--Lookahead control in the IBM System 
370/165, Computer no. 11, vol. 7, Nov. 1974; Thornton, I. E.--Parallel 
operation in the Control Data 6600, AFIPS Proc. FJCC, part. 2, vol. 26, 
1964, pp.34-40). 
However, pipeline structures are sometimes inefficient because the large 
percentage of branch instructions (about 25%) frequently slows down the 
pace further the line should be emptied of those instructions which had 
previously been taken from memory. The interrelations between instructions 
often cause deadlocks in processing. With different servicing time for the 
constituient units of the connecting line the only way of rendering the 
line throughput uniform is to use several units installed at one line node 
for parallel operations which makes control difficult. Also on the 
interrelations between instructions often does not allow an efficient use 
of the units installed to run in parallel. Given the complexity and the 
temporal character of the instructions, a range of few cycles to tens of 
cycles, their lack in uniformity bears on the performance of the equipment 
and complicates its supervision. The method best applies to those systems 
where processing is highly uniform (vector processing, array processing, 
image processing, etc.) and is mainly associated with supercomputers 
(Weiss, S., Smith, J. E.--Instruction issue logic in pipe-linead 
supercomputers, IEEE Trans. on Comp., C-33, no. 11, Nov. 1984). 
Parallel processing with several processors of which interconnection is 
made by one of the well-known methods (Zakharov, V.--Parallelism and array 
processing, IEEE Trans. on Comp., Jan. 1984; Georgescu, I.--Communication 
in parallel processing systems, Studies and Researches in Computer and 
Informatics, vol. 1, no. 1, March 1990): shared memory (common bus, 
crossbar switch) or network (tree, ring, array, hypercube, etc.) is 
characterized by the fact that a plurality of stand-alone processors, each 
of them processing an individual job, are connected in a geometrical 
configuration. A common bus connection of several processors to a memory 
limits the configuration to that bus throughput, thus making it a critical 
point of the structure. As to those configurations that make use of a 
crossbar switch, enabling the access of each processor to each memory 
module, they have the handicap of a complex interconnection system, the 
complexity of which increases with the product of the number of connected 
devices. With different types of networks (tree, ring, torus, hypercube, 
etc.), the distribution, communication and supervision of processing jobs 
come to play a decisive role as the network size increases. One of the 
best known achievements in this field connects in a hypercube-like network 
64K nodes, each node including a 4 kb cell memory and a low-granularity 
processor which works with a limited set of instructions on a few bit 
operands. A network communication unit is host to each 16 nodes. (Hillis, 
D. H.--The Connection Machine, MIT Press, Cambridge, 1985). The main 
characteristics of this system include a low-granularity of the processor 
which narrows its applicability to peculiar problems (large size vectors 
and other similar data structures) and makes performance are highly 
dependent on the aplication area. The performance will be poorer if the 
problem distribution over the structure is badly made. On the other hand, 
a fine granulation involves the need for higher level of data transfer 
within the network. Programming such a network, using it and communicating 
within it raise problems which may not be solvable. Machines with 
high-granularity conventional processors whose structure is not necessarly 
uniform, but, since the existing networks do not solve the communication 
problems, such a network seldom includes tens or at most hundreds of 
processors. (Hockney, R. T., Jesshope, C. R.--Parallel computers, Adam 
Higler Ltd., Bristol, 1981). 
OBJECT OF THE INVENTION 
It is an object of the invention to provide in achieving a network 
structure for parallel processing of logic programs, capable of solving 
the communication problem as well as facilitating solution to other 
processing job distribution and supervision. 
The network architecture for parallel processing of logic programs, in 
conformity with the invention, makes use of a connection in a network 
topology where the nodes include large size memory units which allow 
several processing units, operating on the network edges intersecting at 
that node, have concurrent access to them. The processing units provide 
many high-granularity virtual processors capable of both carrying out 
processing jobs on the two memories connected to the processing unit and 
transfer ring jobs between the two memories bridged by the respective 
processor. 
The processing unit is composed of a program activation unit which includes 
a program address stack and can exercise the control over the current 
instruction location computation, over the execution of jumps and over 
program state changes, a memory instructions reading unit which receives 
the orders from the program activation unit and retrieves instructions 
from the memory or from its cache memory and stores them on instruction 
buffers within an order interpretation block which receives instructions 
from the instructions buffers, analyzes them, compute the operands' 
addresses and stores them on a register access buffers situated at the 
input of a general register block or on a memory access buffers situated 
at the input of a memory operand reading unit, equipped with a cache 
memory. The general register blocks, after the operands are read, store 
them in operand buffers situated at the input of an execution block which 
takes over operands from the operands buffers, execute the required 
operation and stores the result on a general register writing buffer which 
can write the result in the general register block and at the same time 
update block. The processing unit also includes executes the transfer of 
data between the two memory units to which the processing unit is 
connected, and a control unit receiving, via the memory connection buses, 
the control commands for start, stop and testing of the processes from the 
processing unit, to each process being allocated one virtual processor 
obtained by virtualizing the shared installed physical resources. 
The invention has the following advantages: 
it enables parallel job processing at procedure level, high granularity of 
processing, with easy distribution and efficient control of the jobs to be 
processed in parallel; 
it uses large clusters of processors with shared memory communication 
within the clusters and diminished communication between clusters via a 
network; 
it constitutes an efficient communication network, of which throughput and 
communication channels are adapted to traffic requirements, network 
redundancy and reliablity; 
it allows use of processing unit with best sizing of the installed 
equipment, taking into consideration the instruction set parameters, the 
technology applied, the algorithms used, their modularity contributing to 
developing reliable and fault-tolerant units; 
it enables the use of a processing unit whose homogeneous and modular 
structure helps in designing the integrated circuits and; 
the parallel processing systems' performances do not depend on the 
structure of the data to be processed (whether regular or not).

SPECIFIC DESCRIPTION 
The network of the invention has large size memory units M0, M1, M2, M3 . . 
. at the network nodes connected by several processing units UP0, UP1, 
UP2, UP3 . . . installed in the network branches intersecting at that 
node, with concurrent access to each node. Each processing unit 
representing a large number of virtual processors for carrying out 
processing jobs on both of the two memories connected by the processing 
unit and transferring jobs between the two memories connected by the 
processing unit. Each memory unit has an interprocess control block 
contributing to the communication process in the network. 
FIG. 2 presents the diagram of the connection of two nodes in the 
processing network where M0 and M1 memories are located, explaining the 
P0, P1, . . . , Pn-1 virtual processors represented by the UP0 processing 
unit, the clusters of 6*n processors existing in each node (n stands for 
the number of virtual processors developed by a processing unit), as well 
as the n communication channels to the neighboring nodes where memories 
are located, marked by M in FIG. 2, based on n virtual processors, any of 
them being capable, depending on the current demands, of performing 
processing or transfer jobs on the two memories, to which it is connected. 
Instructions are available within the same program in both memories a jump 
instruction will be used for going from one sequence to the other. 
Two processors in a cluster of processors around a node will communicate 
with one another via the memory located on that node (shared-memory 
communication). Two processors, no matter which, in various clusters of 
the network will communicate with one another as follows: the emitter 
process stores the message structured according to an interprocessor 
communication protocol in the memory. From there the message is sent via 
network, based on the "store and send" principle. In order to take place, 
the process is initiated by the processor which the emitter process runs 
on. It activates an interprocess control block which is part of any memory 
unit in each node. The command, the processor location, the type of 
command instruction, etc. are sent by access buses to one of the two 
memory units to which the process is connected, as required by the 
communication procedure. Once activated, the interprocess control block 
sends a command instruction for process interrupt and switching to the 
virtual processor of which address has been previously received. The 
virtual processor addressed by the command switches the process on the 
communication procedure, within which there takes place the required 
transfer between the two memories to which it is connected. Once the 
transfer is completed, an algorithm helps in selecting the address of that 
virtual processor which is going to carry on the communication process and 
through the access bus to the memory unit taking the message is sent the 
chosen virtual processor address and the command for activating the 
interprocess control block connected to the memory. When the communication 
procedure is over, one switches on the interrupt process. Further, the 
procedure takes as many iterations as necessary for the message reception 
by the addressee. 
According to our invention, the processing unit (FIG. 3) is composed of 
program activation unit, UAP, which includes a stack of program addresses 
and a control for the current instruction address computation, for the 
execution of jumps, for program state changes based on the operation 
parameters' situation and on the indications of a record block called 
BEVI. The program activation unit also acts as a mixer for processing 
programs combining a progresive scanning of programs with a launching into 
processing, in sequential cycles of, one instruction or two instructions 
(as allowed by the process state) of each program. 
A memory instruction reading unit, UCIM, takes over the orders from the 
program activation unit and retrieves the instructions from memory, unless 
they are present in a cache memory with which the unit is equipped. A 
block of instruction buffers, TI, receives the instructions read by UCIM. 
An order interpretation block, UIO, receives the instructions from the 
instruction buffers, interprets them, computes the operand' addresses and 
stores these associated with the type of job, the execution unit address 
and other parameters indicating the way the job is executed in the 
register access buffers TAR, or in memory access buffers TAM, except for 
the jump instructions when the jump address is sent to the program 
activation unit where the jump operation is executed. 
A general register block BRG includes general registers and has two 
stand-alone access gates for reading, if accessed by TAR buffers, and for 
writing, if accessed by register writing buffers, TRS; the gates are 
controlled by a priority access mechanism. The read operands are sent via 
a data bus MAG 1 and stored on operand buffers TUER. A memory operand 
reading unit UCOM, following the access queries in TAM and, in the case 
that the information is missing from a cache memory, with which the unit 
is equipped, it starts the access procedure to the memory and sends the 
read operands via a data bus MAG 2 and stores them on operand' buffers 
TUEM. An execution block BE, includes execution units per types of 
operations, each type having an appropriate number of execution units 
installed so that the required processing throughput should be obtained. 
The TUER, TUEM buffers deliver the operands, the type of operation and the 
parameters on how the operation is processed and the execution block 
executes the operation and sends the result on a data bus MAG 3 for 
storage in the register writing buffers TRS. Besides storing the result in 
the general register block BRG, the register writing buffer TRS update 
certain operation parameters existing on the records block BEVI, an 
forming a control system for the whole processing unit. This control 
system covers all the units of the processing unit, the buffers and buses, 
and is based on parameters, addresses, labels for the instructions and 
operands pervading the units. 
A transfer block BT consisting of unit thereby the information is 
transferred between two memory units, M0 and M1, the units being connected 
by two access buses MAM 1 and MAM 2. The transfer orders are taken the 
same way as the execution unit BE takes the current orders. The general 
registers provide the transfer addresses, the amount of data to be 
transmitted; after completing the transfer, the parameters are updated and 
stored in BRG. A control unit UC receives from the access buses, MAM 1 and 
MAM 2, the control commands necessary for the unit process start, stop and 
testing. 
The processing unit combines different types of parallelism: parallel 
processing of a number of programs, instruction of a program being 
parallel processed both by pipeline method and by parallel execution of 
many operations in the execution part. The number of programs is dependent 
on the set of instructions, features of instruction (addressing, 
complexity, etc.), the algorithms used in execution part, the technology 
used, the expected performances, the statistical features of phenomena in 
the processing unit, etc. The instructions of the programs to be processed 
are combined with one another by a progressive scanning of programs, with 
one or two instructions provided by each program in successive cycles, 
accordingly with the state of corresponding processes. In this case the 
flow will run without any interrelations between the successive 
instructions pertaining to various programs--an ideal situation for 
processing in a pipeline structure. The steady-state is achieved because 
of a large number of running programs and the phenomena in the processing 
unit will be statistically processed and the installed equipments will be 
rigorously dimensioned. Thus, the programs share the installed physical 
resources, organized on a pipeline structure, the resources being assigned 
only temporarily, accordance with momentary need. By this treatment the 
physical resources are virtualized: each program will be assigned a 
virtual processor, their connection being a shared-memory communication 
type with one single bus for getting access to a memory and the 
possibility for accessing two memories where processing or transfer jobs 
between the two memories can take place concurrently.