Undergraduate Projects for 2000

Parallel Computing Research Laboratory  

 
 
 

1. Artificial Life Techniques for Task Scheduling in Parallel Computing Environments

Scheduling and load-balancing are two important problems in the area of parallel computing. Efficient solutions to these problems will have profound theoretical and practical implications that will affect other parallel computing problems of similar nature. Little research attempted a generalized approach to the above problems. The major problems encountered are due to the interprocessor communication and delay because of inter-dependency between the different subtasks. The mapping problem arises when the dependency structure of a parallel algorithm differs from the processor interconnection of the parallel computer, or when the number of processes generated by the algorithm exceeds the number of processors available. In this project we intend to investigate the potential of applying new classes of algorithms known as "Artificial Life" techniques (e.g. genetic algorithms, ant colonies, fuzzy logic, etc) in solving the scheduling problem. A-Life methods are playing an increasing role in studies of complex adaptive systems, ranging from adaptive agents in economic theory to the use of machine learning techniques in the design of complex devices such as aircraft turbines and integrated circuits.
 

2. Parallel Artificial-Life Algorithms for Solving Routing Problems

The design of multilayer printed circuit boards (MPCB's) is of great importance in the design of complex electronic systems. MPCB design and layout involves the following steps: (1) placement of the functional modules of the system on the MPCB, and, (2) conductor routing, subject to various physical constraints, on the MPCB to effect the necessary interconnections between the modules. Clearly, these two steps are closely related. However, the complexity of the total layout problem is so great that, traditionally, these two steps have been treated separately. The second problem (in 2 above) is a classical problem in computer aided design, such as the carriers routing in MPCBs or ICs chips (integrated circuits). Despite the fact that more and more CAD packages for layout are available these days, the circuit layout problem is far from solved. In this work we intend to address some aspects of the routing problem by using Artificial Life techniques (e.g. genetic algorithms). Furthermore, because A-life methods are inherently parallel in nature, any proposed solutions to solve the routing problem should be easy to implement on a parallel platform.
 

3. Parallel Computation of Robot Dynamics

Robot dynamics algorithms are essential tools for the real-time modelling and control of robot manipulators. This project deals with the execution of well-known robot dynamics algorithms (e.g. Newton-Euler, Recursive Lagrangian) on parallel processor platforms. The chosen parallel architecture in this case is a mesh with multiple broadcasting (MBB). The MBB is a powerful parallel architecture that was proposed recently and a number of prototype systems were built to prove its practicality. The developed algorithms will be compared to their sequential counterparts and other parallel implementations.
 

4. Using (mobile) Agents in Mobile Computing

Recently, a new approach for learning features of a domain of interest has been proposed. The main characteristic of the novel approach is the fact that global information about the domain is obtained by combining in some clever way local information gathered by independent agents. In fact, for a large number of practically-relevant domains the following paradigm can be used: (1) a large number of agents, each with a specific mandate is being sent into the domain, (2) each agent learns a given characteristic or feature of the domain, (3) a subset of the agents is recovered and debriefed. Somewhat surprisingly, for many domains it is possibly to recover a strict subset of the agents and still obtain FULL knowledge about the domain. It would be very useful to implement strategies for a-c above for a number of particular domains arising in various practical applications. Of a particular interest is the area of mobile computing and wireless networks.
 

5. Computation of Kalman Filtering Algorithms on Reconfigurable Meshes

Kalman filtering algorithms are simple yet powerful algorithms that can be used in a wide range of applications (e.g. image processing, speech synthesis, controller design). Such algorithms need to be implemented in real-time in order to be of any use. One approach to speedup such algorithms is to implement them on parallel hardware. This projects aims to utilize the "Reconfigurable Mesh" in enabling in situ Kalman filtering computations. The RM is a modified mesh with a dynamic reconfiguration capability that can be used to deal with real-time problems.
 

6. Development of Algorithms for DNA Computers

This project is concerned with the possibility of developing techniques for massively parallel computing at the molecular scale. It has been shown in the literature that computations at the molecular level can take place by using short DNA strands. This is practically attainable by using standard biotechnology engineering techniques. This project will attempt to study a number of fundamental algorithms (e.g. Convex Hulls, Prefix-Sums, and others) and try to develop parallel DNA-based algorithms to improve these methods. Comparisons will also be made to compare traditional parallel algorithms and DNA-based ones.
 

7. FPGAs Implementation of Neural and Genetic Algorithms

Neural network and genetic algorithms are used extensively to solve a wide range of problems. There is a great need to test whether these algorithms are suited for implementations. One approach to test this is to use Field Programmable Gate Arrays (FPGAs). This project aims to implement some basic neural and/or genetic algorithms using FPGAs and study issues relating to the ease of implementation and efficiency.
 

8. Deadlock Avoidance in Multistage Interconnection Networks

The dynamic nature of multistage interconnection networks makes them suitable candidates for constructing massively parallel computing systems. In such interconnects there is a need for the on-line detection of hot spots (congestion spots). In this case, a packet needs to be routed in a manner that avoids hot spots. This problem is very similar to a robot (packet) moving in an environment (network) and trying to avoid obstacles (hot spots). This project will investigate this link between these two problems to try to arrive to efficient solutions that can be used to solve problems of this nature.
 
 
 
Questions should be addressed to Professor Albert Y. Zomaya.

This page was last updated on December 8, 2000.
Back to the lab's home page