In either sequential or parallel systems, the architecture is characterized
by functional components, the communication topology and facilities, and
control structures and mechanisms. However, there are several issues related
to parallelization that do not arise in sequential programming. One of
the most important issues is task-allocation, that is the breakdown of
the total workload into smaller tasks assigned to different processors,
and the proper sequencing of the tasks when some of them are interdependent
and cannot be executed simultaneously. To achieve the highest level of
performance it is important to ensure that each processor is properly utilized.
This process is called load-balancing or scheduling and it is considered
to be extremely "formidable" to solve. The scheduling problem belong to
a class of problems known as NP-complete. The aim of this project is to
develop efficient techniques to automate the mapping and scheduling of
parallel tasks onto networks of ! parallel processors.
Multilayer printed circuit boards (MPCB's) design and layout involves
the following steps: placement of the functional modules of the system
on the MPCB, and conductor routing, subject to various physical constraints,
on the MPCB to effect the necessary interconnections between the modules.
This work addresses some aspects of the routing problem by using heuristics
and genetic algorithms. Given module locations on the MPCB and lists of
points to be made electrically common, one is concerned with the definition
of the conductor paths on the MPCB that satisfy all the requirements and
constraints. The routing problem in its general form is known to be computationally
intractable, and an efficient solution of this problem will have a great
impact on other problems of similar nature (e.g., scheduling, networking).
By moving much of the burden of decision-making from the compiler to
the runtime system it is hoped that: (i) compiled programs can be made
portable across multiple platforms, (ii) greater parallelism can be extracted
and hence performance increased, and (iii) sparse or irregular problems
that defy compile-time analysis can be handled efficiently. The runtime
system currently being developed as part of this project will support both
data- and task-parallel models of computation and is aimed initially at
message-passing MIMD architectures. It is hoped that it will represent
a further step down the path towards fully automatic program parallelization
and compilation.
The main aim of this project is the speeding up of computationally-intensive
robotic algorithms. These algorithms cover a wide range of operations:
kineamtics, dynamics, path planning and trajectory generation, and vision,
to name a few. This project investigates computational algorithms for both
fixed-base and mobile robots. Techniques based on genetic algorithms, fuzzy
logic, and neural networks are used to solve the path planning and trajectory
generation problems and then the resulting algorithms are mapped onto networks
of parallel processors. Heuristics are also used for the parallel computing
of robot kinematics and dynamics.
Back to the lab's home page