SOME POSSIBLE PROJECTS

(Dissertation, Thesis, MA-Project, etc.)

1. (Thesis/Project) Prepare a user’s guide for the WorldScape board. Useful features could include

a. An efficient implemention of the needed ASC functions (PickOne, AnyResponders, Global MAX/MIN, Global AND/OR, etc).

b. Efficient implementation examples for several ASC algorithms (preferably of different types) on the WorldScape Board.

2. (Thesis, but may be able to expand into dissertation). Design a new compiler for ASC

a. Would be preferable to automatically generate this compiler (e.g., using YACC & LEX) UNIX utilities).The O’Reilly reference book on generating compilers is an excellent reference.

b. It will be easy to extend the ASC compiler into a MASC compiler that supports multiple instruction streams using the Manager-Worker paradigm.

c. If add OOPs features, etc. could be a dissertation topic

3. Implementing a SIMD Air Traffic Control simulation. There are several aspects to this problem. Related projects could involve several people.

a. Search for relevant literature on this problem and become familiar with various aspects relevant to this project.

b. Determine reasonable requirements for this simulation to satisfy

c. Design data structure algorithms for implementation on our WorldScape board and code them in a high level language (Cn).

d. Consider speed and space optimizations and possibly use of sorting to speed up.

e. Test correctness of program and get some timings (preferably using an ATC simulator available from one of Dr. Welch’s past Ph.D. graduates

f. Write reports and papers.

g. Possibly work with WorldScape in moving implementation to the CSX600 board.

i. Get timings using ATC simulator

ii. Write reports and papers

iii. have demonstrations, etc.

h. An independent step is to learn more about the interface between distributed portion of ATC and its interface with the “computed intensive” portion and prepare a summary of how the interface between distributed and SIMD portions works.

4. Investigate implementation of other useful real-time systems using SIMDs.

a. One approach is to try to identify other real-time systems that could be probably be solved using an approach similar to the preceding SIMD ATC approach.  Typical examples are

i. Navy’s ATC-like software for aiding and controlling aircraft in tracking and intercepting targets.

ii. Delivery of spoilable food into U.S. ports that have to be checked out for safety in a way that minimizes spoilage.

iii. (Bioinformatics) Modeling a cell and the active particles that are active in the vicinity of this cell.

b. Another approach is to look first for interesting and industrially attractive real-time problems and then try to find a SIMD solution for them that is better, faster, and much cheaper.

c. In either case, plan to implement a simulation of solution on the WorldScape board or a Zephyr SIMD.

d. Bioinformatics applications that are of interest to Dr. Lonnie Welch.

5. Develop new ASC and/or MASC algorithms.

a. Normally develop an ASC algorithm first. (May be able to extend an ASC algorithm to one or more MASC algorithms).

b. MASC algorithms could either assume a small number of instruction streams (e.g., 2-8) using the Manager-Worker paradigm or could assume large fixed number (e.g., lg(n) ISs).

c. Examples include FFT, Computational Geometry algorithms, etc.

6. Investigate other paradigms other than specific Manager-Worker technique Wittaya is developing to manage a limited small number of instruction streams (e.g., 2-8) for the MASC model and compare performance with the Manager-Worker model.

a. This could involve variations  on the Manager-Worker model Wittaya is developing.

b. Would need to compare performance with Wittaya’s technique.

7. Develop algorithms for a cluster of SIMDs. Implement and test on our cluster of Zephyrs. This is a new model that may prove quite useful.

8. Develop new parallel algorithms for problems that you find interesting. You would need to choose an appropriate model of parallel computation (e.g., shared memory multicomputer) for your problem. In some cases (but not all), implementing these algorithms may be desirable. These could include

a. Interesting applications

b. Theoretical areas (graph theory, computational geometry, etc.)

c. Bioinformatics areas

9. Investigate PRAM-MASC simulation algorithms. Possibilities include

a. Review and possibly extend current “average time” simulation algorithm of PRAM using MASC (by Darrell Ulm).

b. Develop an average time simulation of MASC using PRAM (i.e., the reverse direction of Ulm’s simulation).

c. Develop “worst case” simulation algorithms between MASC and PRAM.

10. Develop a parallel version of the Molecular Topological Similarity Analysis algorithm TOPSIM that has been developed in collaboration with Professor Tsai in the Chemistry Department.

a. An implementation on a cluster would be a very useful project.

b. A more challenging task would be to develop a parallel version of this algorithm for SIMDs.

11. Perhaps some of you may think of a project that you would like to do that involves parallelism. If so, please discuss it with me.

Please contact Dr. Johnnie Baker for more information