Parallel Processing

The purpose of the current web-page is to present parallel machines that can be implemented by an amateur electronic. A set of implementations of some parallel algorithms in these machines is also presented. The implemented algorithms are well known and presented in details in the literature. However, this page presents implementations using real code. This way it may be easier for someone to understand the function of the algorithms as well as to reveal any difficulties found when one tries to implement the algorithms in reality.

A summary of some basic parallel processing aspects (related to the code presented in these pages) may be useful. For an extended study we suggest the book of F. Thomson Leighton, “Introduction to parallel algorithms and architectures: arrays, trees, hypercubes,” Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991."

Two machines have been designed and constructed:

- The first machine with name "Array of MCU" uses as a basic processing unit the AT89S52 from ATMEL that is a 8051 clone. The prototype machine can use up to 16 processing units. The processing elements communicate with each other through 8-bit words that are transmitted (and received) in one cycle. Each processing unit can communicate with at most 4 other units. The machine is considered too OLD and the documents have been removed from this site.

- The second machine with name "Parallel PIC" uses as a basic programming unit the PIC24FJ16 from MICROCHIP. The prototype machine uses 8 processing units. The processing elements communicate with each other through serial ports (UARTs). Each processing unit in the prototype machine can communicate with at most 12 other units.

During the development of the programs that implement algorithms in the parallel machines, some common aspects have been revealed. The treatment of these aspects gives an insight in programming parallel machines. We believe that the abovementioned discussion will be useful for anyone that tries to develop real programs for real machines.

For each algorithm an implementation is presented in one or more of the parallel machines. The algorithms developed so far are:

1) Sorting on a linear array (I/O from first and last Processing Elements) (Parallel PIC).

2) Sorting on a linear array (I/O in each Processing Elements) (Parallel PIC).

3) Integer Sum on a Binary Tree (Array of MCU).