Parallel Algorithms for Processor Clusters, Multi-Core Processors and GPUs

This research project studies the design, implementation, and testing of parallel methods for solving hard computational problems on parallel computing platforms.

Most of today's parallel machines are either processor clusters or multi core processors, or combinations of both.

A processor cluster is a set of standard workstation type machines connected via a fast switch. Multi core processors are single chip architectures that contain multiple processor cores. In order to allow effective programming of such parallel machines, new programming paradigms and methodologies are required.

HPCVL Cluster

Our Coarse Grained Multicomputer (CGM) model has become a popular tool for designing efficient algorithms for processor cluster. CGM algorithms have a fixed small number of large messages, resulting in a fixed small communication overhead that shrinks proportionally as data size increases. They also have only very few threads per processor which reduces context switching overheads and allows for algorithmic approaches such as large scale sampling. The journal Algorithmica has dedicated two entire special issues [1,2] to our CGM model.

The recent arrival of multi-core processors (e.g. Intel multi-core) and many-core GPUs (e.g. high end nVIDIA and AMD graphics cards) has brought a significant boost to parallel computing. For example, recent nVIDIA graphics cards provide 200+ processor cores at a cost of around $400. This allows to build parallel machines at a new scale. It also makes the algorithmic challenge to make efficient use of this new hardware even more significant.

Intel Multi Core Processor

Parallel computing is about solving hard computational problems that require large amounts of computation or process large amounts of data, or both. To apply our parallel programming paradigms and methodologies, we have chosen the following research problems:

• Parallel Computational Geometry

• Parallel Data Warehousing and OLAP

• Parallel Bioinformatics

GeForce 260 GPU
with 216 Cores

Triple GeForce GPU
with 600+ Cores