copy a processor state

This function generates a move code program to compute the factorial of a given number n. It makes use of three PUs and runs in linear time.

This function generates a move code program to compute the sum of the first n natural numbers with puNum PUs. The generated move code program has 3*n-3 instructions and can be run with log(n)+1 many steps with n/2 many PUs. However, it requires a large issue width of about 4 times the number of PUs. A buffer size of 2 is however sufficient for optimal time.

OddEven Transposition Sorting is a parallel sorting algorithm that requires O(n^2) work with a depth of O(n). The compare-and-swap operation is implemented by comparing x1 with x2, and conditional assignments to variables y1 = b1 and x1 or !b1 or x2 and y2 = !b1 and x1 or b1 or x2. Without leveling, the program results in a dataflow graph which cannot be scheduled on a single PU; however, two PUs are sufficient to run the program. In addition to this PU, we need another PU that provides the input pair of values for this operation, and will afterwards pick the result to insert in the sequence.

This function generates a move code program for computing the parallel prefix sum of the first n numbers. The function uses only a single PU and processes the levelized dataflow graph level by level from left to right. The values are thereby kept in the left input buffer and are either copied back to this buffer, duplicated for a following addition, or added to a valued put in inR after a previous duplication. The algorithm implements the Brent-Kung parallel prefix tree which is work and time optimal.

Kogge-Stone parallel prefix computation is not work-efficient, but almost twice as fast as the Brent-Kung parallel prefix computation. On SCAD, the additional work does not matter since the Brent-Kung implementation may require additional COPY operations as well. The implementation makes use of two PUs, since we need to duplicate the result of additions while having the values of the current level in the inL buffer of PU[0].

This function generates a move code program to compute the sum of the first n natural numbers with puNum PUs. The generated move code program has 3*n-3 instructions and can be run with log(n)+1 many steps with n/2 many PUs. However, it requires a large issue width of about the number of PUs. A buffer size of 2 is however sufficient for optimal time.

generate an initial state for the processor

split a move code program into threads, i.e., move code instructions that have to be sent to each PU

determine the number of PUs used by the given move code program, e.g. to assign the mutable variable numPU in this module

This function computes the number of PUs used by the program and then it computes the minimal issue width and buffer size to achieve the minimal runtime of the program. Note that the minimal runtime can be achieved if the processor may issue all instructions in the first step.

parse a move program from a file

parse a move program from a stream

parse a move program from a string

write a byte array to a binary file

Print the threads per PU of a move code program

This function prints a SCAD machine simulation trace as generated by ScadExec in html output format.

This function is used to generate a simulation trace for a given move code program. Make sure that the mutable values numPU, bufSize, and memSize of this module are initialized accordingly; you may use function NumberOfPUs to determine the number of PUs used by the given program. Parameter maxIssue determines the maximal number of move instructions issued by the CU in one step (it may issue less if the buffers are full). Parameter maxSteps provides an optional upper bound of steps for the simulation; if it is None, the program runs up to termination. The result is a list of triples (numFirings,numTransfers,psState) where numFirings holds the numbers of firings of the PUs up to this point, numTransfers is the number of data transfers up to this point, and psState is the processor state at that point.

Upscaling a Move Code Program to a given number of PUs. Note that any PU allocation remains valid by any partition refinement, i.e., nodes that are mapped to different PUs before must also be mapped to different PUs afterwards, but nodes that are currently mapped to the same PU may be moved to new PUs without producing conflicts unless the new PU is not used for nodes currently mapped to other PUs as well.

write a byte array to a binary file

write move program to a text file

write a byte array to a text file

size of the buffers

latencies of the instructions

size of the data memory

The value numPU in this module must be initialized with the number of general purpose PUs (without CU and LSU) to ensure a correct instruction encoding.