Type of the control unit of a SCAD machine.

this execption is thrown when enqueuing an entry to a full buffer

MoveUniInstr defines the type for move instructions. There are four types of move instructions:

• MoveOutBf2InpBf(src,tgt) denotes a move from output buffer src to input buffer tgt.
• MoveConst2InpBf(v,tgt) denotes a move of value v to input buffer tgt.
• MoveOpc2PU((op,nc),adrU) denotes a move of opcode op and number of copies nc to the optional lane of processing unit adrU.
• MoveOpc2LSU(op,nc) denotes a move of opcode op and number of copies nc to the load/store unit's optional lane. nc has to be a dummy value for store operations (not used but required).

Processing units generally consist of an input and an output buffer having possibly different numbers of lanes. In contrast to the output buffer, the input buffer may have an optional lane.

A SCAD machine consists of the following components:

• CU is the control unit which reads move instructions from the program memory. It is also responsible for branch and jump instructions, and uses three lanes in its input buffer for this reason:
  • CU.inp[0] is the branch condition lane.
  • CU.inp[1] is the `then' branch target lane.
  • CU.inp[2] is the `else' branch target lane.
  As long as a pc is available in CU.pc, the corresponding move instruction is fetched and issued, and this pc is incremented. Branch instructions are implemented as follows:
  • First move the branch target address to CU.inp[1].
  • Next, issue move instructions to compute the branch condition.
  • Finally, there is move instruction from an output buffer to the CU.inp[0]. If this instruction is issued by the CU, the CU will destroy its CU.pc (making it None), and will move pc+1 to CU.inp[2].
  • If CU.inp can fire, a new pc can be taken, and new instructions can be fetched again.
  The CU stops issuing further instructions as soon as the pc is outside the allowed addresses of the program memory.
• PU is an array of universal processing units for processing binary operations. Each PU has one input and one output buffer with the following lanes:
  • PU[i].inp.valEntry[0] holds the left operands of binary operation.
  • PU[i].inp.valEntry[1] holds the right operands of a binary operation.
  • PU[i].inp.optEntry holds the opcodes and number of copies.
  • PU[i].out.valEntry[0] holds the result values.
  Each PU registers the move instructions issued by the CU whenever the address is either the source or target address of a move instruction. Moreover, result values are produced whenever input operands are available and there is enough space in the output buffer.
• The LSU is the load/store unit of the SCAD machine with the following lanes:
  • PU[i].inp.valEntry[0] holds the addresses.
  • PU[i].inp.valEntry[1] holds the values to be stored.
  • PU[i].inp.optEntry holds the opcodes and number of copies, where opcode true means load and false means store.
  • PU[i].out.valEntry[0] holds the result values in case of load operations.
• The ROB is the reorder unit of the SCAD machine that is used by the code generator whenever the operands are not found in the right order in the output buffers. It is one input and one output lane and simply copies the values from the input to the output buffer lane (so it is essentially just an additional buffer).
• MemData is the data memory that can be accessed only by the LSU.
• MemProg is the program memory that can be accessed only by the CU.

We use the following addresses of the functional units

• 0: CU
• 1: LSU
• 2: ROB
• 3..n+2: PU for the n universal processing units PU[0..n-1]

address denotes addresses of buffers (processing unit + buffer)

addressBuf denotes addresses of buffers within a processing unit

addressPU denotes addresses of processing units

This buffer class implements the buffers of the processing units inside a SCAD machine where each processing unit has at most one input and at most one output buffer, since each buffer itself can have several lanes for input/output values and even an optional lane having another type of values. Each entry i in an input/output lane bf is a pair valEntry[i][bf]=(adr,v) consisting of an optional address adr and an optional value v, while the optional lanes entries optEntry[i] can store any optional values. The overall buffer works as a FIFO queue and each lanes behave as such in a special was as well: At any time, the entries from head to tail are in use where head and tail are the indices of the first and last entry in use. Since both the empty and the full buffer satisfy tail+1=head, additional flags isEmpty and isFull are used to check whether the buffer is empty or full (it can have at most numRows entries). Enqueue operations work as follows:

• enqAdr(bf,adr) adds address adr to the lane bf: First, the oldest entry (None,*) of the lane is searched, and if it exists, the address is stored in there. Otherwise, a new tail is added to the entire buffer, i.e., to all lanes, and the lane bf has the tail (adr,None).
• enqValInp(src,tgt,v) adds value v to the lane bf where tgt=(tU,bf) holds: First, the oldest entry (src,None) of the lane bf is searched, and if it exists, the value is stored in there. Otherwise, the oldest entry (None,None) of the lane bf is searched, and if it exists, the value is stored in there. Otherwise, a new tail is added to the entire buffer, i.e., to all lanes, and the lane bf has the tail (None,v).
• enqValOut(bf,v,nc) adds nc copies of value v to the lane bf: First, the oldest entry (*,None) of the lane bf is searched, and if exists, the nc copies are added from there on. It may be necessary that new tail numRows have to be added to the buffer to this end.
• enqOpt(bf,x) adds value x to the optional lane: First, the oldest entry None of the lane is searched, and if it exists, the address is stored in there. Otherwise, a new tail is added to the entire buffer, i.e., to all lanes, and the optional lane has the tail x.

All enqueue operations can fail if there is not enough space in the buffer. This can be tested using the functions canEnqAdr, canEnqValInp, canEnqValOut, and canEnqOpt. The dequeue operation reads out the value entries in the lanes of the head of the buffer plus the head element of the optional lane. If some fields of the head row should not be defined, it returns None and leaves the head unchanged.

type value abbreviates values of operands and results