| EPSRC Reference: |
GR/H77811/01 |
| Title: |
A STUDY OF SCALABLE PARALLEL ALGORITHMS FOR LARGE LINEAR PROGRAMMING PROBLEMS |
| Principal Investigator: |
Dew, Professor P |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Sch of Computing |
| Organisation: |
University of Leeds |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 October 1992 |
Ends: |
30 September 1995 |
Value (£): |
120,658
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
To design and analyse scalable parallel algorithms with respect to the PRAM and XPRAM models of computation, for important problems arising in large linear programming problems. To identify the fundamental abstract data types and develop efficient implementations for physical realisation of the XPRAM.Progress:The project is making good progress on understanding the design and implementation of scalable parallel algorithms using the WPRAM model. Two algorithms, one for the simplex method and one for determining the convex hull have been studied in depth and reported in references [1] and [2].The work has proceeded in two main areas. The first has been to refine the definition of the WPRAM model and architecture [3]. A simulator has been built to study the properties of the architecture and enable performance studies to be undertaken. The WPRAM supports a scalable shared addressed space with weakly coherency semantics implemented on a message passing machine with network latency D = O(log P) where P is the number of processors. The model can be used to support a range of algorithms (e.g. BSP and more general MIMD algorithms) and a performance model has been developed to cost the algorithms. A follow-on project will start in April 1995 to implement the architecture on Inmos T9000 processor array. The second part of the work has been to use the WPRAM to design scalable parallel algorithms for the convex hull problems. Our first attempt was to study the implementation of PRAM algorithms. In particular the optimal planar convex hull PRAM algorithm by Aggarwal, Chazelle, Guibas and Yap in Algorthimica 1988 was implemented. This gave very poor results and it was necessary to abandoned this approach in favour of algorithms that had simple and predictable communication patterns, and use randomisation as a load balancing strategy. This has enabled us to design scalable algorithms for sorting (Quicksort) and the planar convex hull problem. Good practical results have been obtained for the WPRAM and the KSR machine at Manchester. The algorithmic techniques will now be extended to further algorithms arising in large linear programming problems. [1] J.M. Nash, P.M. Dew, M.E. Dyer and J.R. Davy Parallel Algorithm Design on the WPRAM ,in Abstract Machine Models for Highly Parallel Computers, April 1993.[2] M.E. Dyer, J.M. Nash and P.M. Dew An optimal Randomised Planar Convex Hull Algorithm with Good Empirical Performance , to appear in the proceeding of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures 1995.[3] J.M. Nash, P.M. Dew and M.E. Dyer, The WPRAM Model for Supporting Portable and Scalable Computations on Messages Passing Machines , submitted to the Journal of Parallel and Distributed Computing and available from the School of Computer Studies.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.leeds.ac.uk |