Home page of Parallel Processing

Ελληνική έκδοση (Greek version)

Integer Sum on a Binary Tree

    We have a binary tree with N Processing Elements (PEs) (where N=2^k-1, k=2 or 3 or 4). The data input is performed at the leaves. Each leaf has two inputs that are 8-bit wide. The sum is outputted at the root with 8-bits width.

    Each PE (leaf, internal or root) reads the input at ports DOWN and RIGHT, performes the sum of these two values and outputs the result at the UP port.

    The code for such a process is:

    The complete source code can be found in file SumtreeA.asm and can be translated and loaded to a single PE for testing. The testing is done using two auxiliary input boards connected to ports DOWN and RIGHT and one auxiliary output board connected to port UP.

    When the program runs the output board must show the sum of the values set from the input boards. Attention: the program performs the sum and the it halts. If we change the input values, the machine must be reset to produce a new correct output!

    We can put the PEs to continously read the input and produce new output. The source code can be found in file SumtreeB.asm:

    Using this code, one can connect more PES in a binary tree and take the sum of all the numbers of the leaves at the root of the tree. Note: as a matter of fact, when the program starts as well as when the input data change, some time must pass before the output will reflect the real sum of the input values. During this time the output must be considered as "non valid".

    If we do not want to have such "non valid" output data, we can make a program that works only "once" (as in the first code presented) and count the time elapsed form RESET till the presence of valid input data. For example, for a binary tree with N=3, the leaves must run the code SumtreeA.asm, while the root must run the following code (SumtreeC.asm):

    The photograph shows the Array Of MCU with 3 PEs (Bottom-Left corner) connected as tree.

Home page of Parallel Processing