Background to The Invention

Everywhere in the industrialised world there is an overwhelining and ever- increasing demand for computers with ever higher speed, greater capacity and improved structures for data control, This requirement may be for purposes of research, space programs, meteorology, database programs, pattern recognition, CAD/CAM, artificial intelligence, neural network models, genetics, to give a few examples only, One obvious way to achieve these objectives is through the development of faster processor technology, e.g. the use of new materials for chip construction, bus communication etc, and the development of designs such as RISC. Another approach is that of parallel processing, in which essentially many processors carry out parts of the same task(s) simultaneously, By the use of such a parallel processing approach a task can be speeded up by many orders of magnitude, even using conventional chip designs,

The invention (method) achieves parallel processing using a new structural principal in the organisation of computers, It is embodied in a chip (the CC-chip specified as the kernel), Though the cardinal principle is one of parallel processing among a plurality of processors, it may be used for many other purposes, e.g. communi ation switching, computer network control, etc. Parallel processing has been attempted in many forms, using hardware, software and mixes of the two approaches, What distinguishes this invention from such previous approaches is the use of a totally dynamic and implicitly self-organising method which transparrently leads to an automatic ordering of events. This ordering is optimal in processing efficiency, allowing the processors to approach the ideal "theoretical

peak" performance as defined by Dongarra in his paper "Performance of Various Computers Using Standard Linear Equations Software." (Mathematical Sciences Section, Oak Ridge National Laboratory, Knoκville USA). To summarise this approach one could say that it implies the structural sorting of chaos into order with coherence, implicitly carried out at the lowest possible level, i.e. machine instruction level,

ThP Stats nf thg Art

To meet the demands for parallel processing many different methods have been developed, and these may be divided into three classes; hardware solutions, software solutions and mixes of the two,

Hardware designs for parallel processing raise many problems involving communication between one or more processors. More or less exotic bus geometries have been attempted, such as rings, stars, hypercubes, butterflies and so on.

Conventional parallel processing systems are extremely expensive in hardware and even more so in software. Hardware solutions may involve elaborate bus structures which raise problems of process scheduling. Software solutions require special parallel programming languages. These need a massive reprogramming effort if existing software is to be reproduced in the new environment. Also programming for parallel processes is very complex, since the three major problems, synchronisation, coherence and ordering of events, have not yet found a satisfactory solution, This is why parallel processing has been up until now for the. very few,

ThP Inventive Step

The CC-syste , according to the invention (method), is original by embodying a method distinguished by a new transparent event ordering system, be it physical and/or logical event ordering, which implies synchronisation and coherence in a recursive manner, thus enabling serial processes to be parallelised. This is achieved by introducing a massive amount of variable sized transparent Queue/Stack cultures named PIPES, spanning the complete address space for which event ordering is needed and dynamically controlled by the QCC-Chip, i.e. the invention is distinguished πd original by being a totally transparent dynamic recursive system adhering to memory management, as opposed to other systems using

Queue/Stack principles.

The CC is a pipe controller with the ability to transparently handle multiple pipes recursively, arbitrarily organized as queues and/or stacks, thus enabling cross referencing between pipes, pipes and their related functions and between functions, It is originated for the purpose of high performance parallel processing, but can be used in any design demanding high performance intercommunication with synchronisation, event-ordering and coherence,

- rns 1 Desrription

Fig, 2 relates completely to this paragraph

The function of the kernel is essentially that of an address handler, which generates the addresses of data in a main memery device according to the sequence of events requesting their access. The kernel performs this function by the use of recursively handled vector pointers to sets of complementary stacks and queues, generically referred to as pipes.

The kernel receives inputs U L F and E, these designating the Upper and Lower vector addresses of pipes, and Full and Empty.queue bits and a Read/Write from a participant bit, a Queue/Stack select bit, a Refocus request bit and a Bit Zero status bit (1 or 0). It also receives an Adders Control which is the value of a pipe step increment/decrement;, ώhich may in the simplest case be unity. The output from the kernel is principally an Address at which data may be found in the memory interlocked between locals, globals and the QCC system, together with Bit Zero which may be a control bit for queue and/or stack selection, and NMI a non maskable interrupt signal.

The mode of operation of the kernel is as follows. If a F & U or an E & RCi.e. full and write or empty and read) condition is present, the status of the Q/S signal is tested. If it is S a non-maskable interrupt is emitted by the kernel. If it is Q then Bit Zero is set to 1 and this is output by the kernel. If neither the F & l ^* . nor E & R combinations is detected, the status of the R/W bit is tested. If it is found to be low (write signal) the status of the Q/S bit is tested. If this is Q the Upper vector adress is immediately asserted as the Address output from the kernel and the

Refocus bit is tested, If the Refocus bit is zero, U is incremented by amount of the Adders Control, The R/U bit is then tested and if it is high (read signal) THE VALUES OF U and L are compared. If they are equal F is set to 1 and if they are unequal F is set to 0. If the value of the R/W bit is low (write signal) the values of U and L are compared. If they are equal E is set to 1 and if they are unequal E is set to 0.

If after testing the F & W and E & R combination the R/W signal is found to be high (read) then the status of the Q/S bit is tested, If it iε Q then L is immediately asserted as the Address output from the kernel and the Refocus bit is tested, If the Refocus bit is zero, L is incremented by the amount of the Adders Control, The R/W bit is then tested and if it is high (read signal) the values of U and L are compared, If they are equal F is set to 1 and if they are unequal F is set to 0, If the value of the R/W bit is low (write signal) the values of U and L are compared, If they are equal E is set to 1 and if they are unequal E is set to 0,

If after testing the F & W and E & R combination the R/W signal is found to be high (read) and the Q/S signal is found to be S, then L iε immediately asserted as the Address output from the kernel and the Refocus bit is tested, If the Refcus bit is zero, L is decremented by the amount of the Addders Control, The R/W bit is then tested and if it is high (read signal) the values of U and L are compared, If they are equal F is set to 1 and if they are unequal F is set to 0, If the value of the R/W bit iε low (write signal) the values of U and L are compared, If they are equal F is set to 1 and if they are unequal F is set to 0, If the value of th R/W bit is low (write signal) the values of U and L are compared. If they are equal E is set to 1 and if theay are unequal E is set to 0,

-ε-

FUNCTION "TABLE

No, EXT .INPUT INT. SIGNAL ADDER QUEUE ADDRESS DECODE REMARK

ADDR Q/s R/w FULL EMPTY FUNCTION STACK OUTPUT SELECT

0 0 0 υ=U+Σ„ STACK URITE i 0 0 Δnnp ^* ■ == < WRITE u u

1 T VOID ***** VOID S7 ERROR STACK

1 1 VOID ***** VOID S7 ERROR

OUFUF WRITE

-[H i

B 1 1 1 VOID ***** VOID S7 ERROR

QUFLJF .ΠΓ.D , — ^•

OUFUE

OUFUF

1 1 1 1 VOID ***** VOID S7 ERROR

INT corresponds to bit ZERO

FULL/EMPTY SELECTION

EXT.INP' T EQUAL FULL EMPTY i . —I tr~.π -.

0 0

0 1 1 0 DEAD STACK ATTEMPT TO WRITE/FULL

1 0 1 1 0 1 DEAD STACK ATTEMPT TO READ/EMPTY

1 0 1 DEAD QUEUE ATTEMPT TO WRITE/FULL

1 1 0 1 DEAD QUEUE ATTEMPT TO READ/EMPTY

FUNCTION EPROM DECODE

No. BINARY CONTEXT ADDER QUEUE ADDRESS DECODE REMARKS

ADDR OUTPUT

0 0 00 0 00 0 0 U=U÷Σr STACK

0 0 0 0 0 0 0 1 L i FULL

1 00 0 0 0 0 0 VOID S7 ERROR

0 0 0 0 0 0 00 -liX) STACK READ

NUH CMDTV

0 0 0 0 0 ADDR:=U

1 00 0 0 0 0 0 VOID ***** VOID S7 ERROR

S 0 0 0 0 00 0 0

A 0 0 0 0 0 0 0 1 rtt itzi iiz Mn~

B 1 0 0 0 0 0 0 0 VOID VOID S7 ERROR

C 00 0 0 0 0 0 0

D 00 0 0 0 0 0 ! INT NOP

E 00 0 0 0 0 0 0

F 1 00 0 0 0 0 0 VOID ***** VOID S7 ERROR

INT corresponds to bit ZERO

UPPER PIPE VERSIOI,

ADDER DECODE

UPPER COUNTER

No , UC Q/5 R/w BINARY CONTEXT REHAR1 ?

ADDR 7-ύ

Decode pattern may alter according to Adders Control

UPPER PIPE VERSION

ADDER DECODE

LOWER COUNTER

No. UC Q/s R/w BINARY CONTEXT REMARKS

ADDR 7-0

o o o o o o o o o o o o STACK URΓTE U DDITIVE

} 0 0 1 0 0 0 00 0 0 0 STACK READ U DEDITIVE

2 0 1 0 0 0 0 0 0 0 0 0 QUEUE URΣTE U ADDITIVE

3 0 1 1 00 0 0 0 0 0 1 QUEUE READ L ADDITIVE a i o o o o o o o o o o

5 I 0 s O O O O O O O O

S r I 0 O O O O O O O O

7 1 1 1 O O O O O O O O UPDATE CYCLE. NO? IN ADDER

Decode pattern may alter according to Adders Control

LQUER PIPE VERSION ftDDER DECODE

U ER COUNTER

D--r-!r...ι LUI.'<I_Λ I

: T ^•*• ,- L --. Γ ^• \--I-Ύ

Decode pattern may alter according to Adders Control

LOWER PIPE VERSION - ftDDER DECODE LOWER COUNTER

No. UC Q/s R/w BINARY CONTEXT REMARKS

ADDR 7-0

0 0 0 0 0 0 0 0 0 0 0 1 STACK WRITE L ADDITIVE

1 0 0 - 1 . 1 1 1 1 1 1 1 0 ! 0 0 0 0 0 0 0 0 0 0 1 T 0 0 0 0 0 0 0 1 QUEUE READ L ADDITIVE } 0 0 0 0 0 0 0 0 0 0 UPDATE CYCLE. NOP ϊN ADDS . 0 1 O O O O O O O O UPDATE CYCLE, NOP IN ADD≡! ϊ 1 0 O O O O O O O O UPDATE CYCLE. NOP IN ADDB 1 . 1 O O O O O O O O UPDATE CYCLE. NOP IN ADDEf

Decode pattern may alter according to Adders Control

Q SYSTEM CHANNEL INTERFACI

LOGICAL PHYSICAL 0 NAME * i CΓI v I.I- -' v-.T i T. IΠ-,I i -' REMARKS

Hm ii— m-

r r. -i -i r, - -ιi ^ - _ι ~,r,r-,- ,- ___,, ,,-

HU rt-51 (-'.'— hi I riu :;: o'. z.

D^Λ-ppi π D ^* rr,_Dcι α rv ^> τ' VTC Π.ΛD ^* I I ^*• "- ^* , ~c p-i'-Tη'i

^** R— ¹ ~ ^~ ~ p -, ^• -- - __.,, I,;

D-.-D1 7

RA

^" 3T

] ;ς_"J O." ~τ z U ^t " ^j ~ u _' ~

* LOWER CASE INDICATES ACTIVE LOW, UPPER CASE INDICATES ACTIVE HIGH

■ - - ^•* - i .

-U-

TH COMPLEMENTARY VECTOR FORMAT

Further annexed hereto is an implementation of the QCC chip kernel, entitled Q. made to the above specification, including Fig. 3, by Derik Renton of EVJ Electronics, thus incidentally demonstrating that a technician who is an outsider can follow the above specifica ion.

Th-a OCC-.ςygtpm - Prinrinlpg nf flppration

The QCC-system is built around two complementarily operating vector memories each with between 512 (minimal system) and 4 giga (maximal in a 32 bit system) entries. Each entry is minimally a &4 bit word, made up of two 32 bit words formatted as shown in "THE COMPLEMENTARY VECTOR FORMAT", page 1-1, These complementary vector memories contains the upper addresses (U), lower addresses (L), queue/stack offset (D), full (F) _; empty (E) status of the queues/stacks and the semaphores (S0- Sn). The semaphores and their purpose may be defined at will by the users and also the word width of the vector memories may be expanded for any purpose, such as restart procedures,

The U contains the upper vector addresses of the queues/stacks. The L contains the lower vector addresses of the queues/stacks both together with their appropriate status being updated as a result of their lasi. operation, according to the rules embodied in the chip design as shown in the drawing named Fig. 2 and descriped in "Kernel Description, page 4" .

Whenever an attempt is made to either write to a full pipe (F=l ) or read from an empty pipe (E=l ) the sequence iε terminated and the address of the vectors concerned is recursively stacked in the neighbouring event pipe, asserted by means of bit zero. The attemptator (the process or thread of a process which attempted the read or write) receives a

signal that an event occurred (interrupted), whereafter the

atte ptator may start a new sequence of operations by recursively reading a new vector address from a stack in the neighbouring event pipe or initiate a new task. The beginning of a sequence is implicit and inherent in the nature of attemptato 's normal interrupt procedure and will succeed when the condition for the termination has been resolved by a process or a thread of a process writing, making it possible to read again (E=0) or by reading, making it possible to write again (F=0) . Thus the system is stochastic and operates transparently and recursively in concordance with e.g. a Markov chain principle, fully exploited to any depth of recursitivity. It can be seen, that the system is alive by any means, i.e. Its logical behaviour is complete towards any condition which may arise, what so ever. It will solve a problem of any complexity, even its own, by its recursitivity, It cannot, by its own rules, produce disorder. On the contrary it will reduce entropy to the minimum possible level, The system may therefore be regarded as an "entropy machine" similar in operation to the concept of a Maxwell demon used to illustrate thermodyna i theory and by Norbert Uiener in his book "Cyberneti s" (page 57),