Home News People Research Study Search

Institute for Computing Systems Architecture

Computer Architecture Simulation & Visualisation

line

ALAMO:
ALgorithms, Architectures and MOdels of computation

Project Summary

The ALAMO Project was funded by EPSRC under Grant GR/J43295 and ran from August 1994 to February 1997

The project set out to address two of the four ``Grand Challenge Problems in Computer Architecture'' identified by the Purdue Workshop on Grand Challenges in Computer Architecture for the Support of High Performance Computing. These are: ``to identify a small number of `fundamental' models of parallel computation that serve as a natural basis for programming languages and that facilitate high performance hardware implementations'' and ``to develop sufficient infrastructure to allow rapid prototyping of hardware ideas and the associated software in a way that permits realistic evaluation.''

Our aim was to combine work on these two Grand Challenges, using Heywood's H-PRAM as the bridging model of parallel computation and our Hierarchical Architecture Design and Simulation Environment (HASE) as the `prototyping infrastructure'. We have devised and refined strategies for implementing the H-PRAM on a physical mesh architecture and have investigated these strategies both theoretically and practically, through simulation.

In order to be able to undertake these simulation we have designed and implemented a Hierarchical Architecture design and Simulation Environment (HASE) which is itself a response to the ``infrastructure'' grand challenge.

HASE

HASE is now a sophisticated and relatively stable environment which we can begin to release as a licensed product to academia and industry.

During the implementation of HASE we investigated the use of a commercial object oriented database as the project data storage facility and found it to be unsatisfactory both in terms of the storage space required and the time required to load experiments into the HASE environment.

In addition to its use for ALAMO, we have used HASE to support a variety of research, PhD, MSc and undergraduate projects. We have also developed a Java version of a subset of HASE, simjava, for use as a WWW-based system and are developing proposals which will make further significant use of both HASE and simjava in the future. simjava has been selected by the Mitre Corporation as a basis for constructing distributed Web-based simulations

Investigating the H-PRAM

Our goals with respect to the H-PRAM were to devise and investigate techniques which would allow the principles of the H-PRAM philosophy to be realized on a more practical underlying architecture, while presenting the programmer with the simplicity of the H-PRAM conceptual model. To this end we have achieved a number of results. We have experimentally investigated the use of $2$-universal hashing as the supporting memory management technique within each sub-PRAM and presented new lower bounds on the underlying random destination routing problem which will be of wider interest. We have investigated (theoretically and experimentally) the use of Hilbert space-filling curves to support the processor mapping mechanism and have tightened existing bounds on the process, while demonstrating that the resulting routing can be supported cheaply and efficiently. We have also begun to investigate the issues involved in extending our approach to exploit higher dimensional meshes. We have devised and analysed a general purpose synchronization mechanism applicable to both synchronization of processor groups (which may be physically disjoint within a sub-PRAM) and the special case of partition-wide synchronization. Again, our technique has applications in the support of other abstract programming models. We have addressed issues relating to the design of an H-PRAM programming language, and have implemented a prototype language. This has been used to experiment with a number of realistic programs.

Results

The H-PRAM successfully outperformed the PRAM by a factor which was small but significant (2 to 3 for the sizes of mesh (typically 1024) we were able to simulate) and which, importantly, was clearly growing with the number of processors involved, thereby demonstrating improved scalability.

Publications

  1. R.N. Ibbett, T. Heywood, M.I. Cole, R.J. Pooley, P. Thanisch, N.P. Topham, G. Chochia, P.S. Coe, P.E. Heywood, Algorithms, Architectures and Models of Computation (postscript), University of Edinburgh, Technical Report, ECS-CSG-22-96. 1996.
  2. A.R. Robertson and R.N. Ibbett "HASE: A Flexible High Performance Architecture Simulator", Proc HICSS-27, Hawaii, 1994, IEEE.
  3. R.N. Ibbett, P.E. Heywood and F.W. Howell "HASE: A Flexible Toolset for Computer Architects", The Computer Journal, Vol 38, (10), 1996.
  4. F.W. Howell, R. Williams and R.N. Ibbett, "Hierarchical Architecture Design and Simulation Environment", MASCOTS-94, IEEE Computer Society Press, 1994.
  5. P. Heywood, P. Thanisch and R. Pooley "Object-Oriented Database Technology for Simulation Environments", Proceedings UKSS '95, Vol 2, North Berwick, April 1995.
  6. R.J. Pooley and P. Thanisch, "Object Oriented Simulation and Object Oriented Databases", EUROSIM Simulation News Europe, No 14, July 1995.
  7. P.E. Heywood, G. MacKechnie, R.J. Pooley and P. Thanisch, "Object Oriented Database Technology Applied to Distributed Simulation", Proc. EUROSIM Congress '95, Vienna, Elsevier, 1995.
  8. P.S. Coe, L.M. Williams and R.N. Ibbett "An Interactive Environment for the Teaching of Computer Architecture", ACM SIGCSE/SIGCUE Joint Conference on Integrating Technology into Computer Science Education, Barcelona, June 1996.
  9. R. McNab and F.W. Howell, "Using Java for Discrete Event Simulation", Proc. 12th UK Computer and Telecommunications Performance Engineering Workshop, Edinburgh, 1996.
  10. P.S. Coe, F.W. Howell, R.N. Ibbett, R. McNab and L.M. Williams, "An Integrated Learning Support Environment for Computer Architecture", 3rd Annual Workshop on Computer Architecture Education at HPCA-3, Texas, 1997.
  11. L. Williams and R.N. Ibbett, "Simulating the DASH Architecture in HASE", Proc. 29th Annual Simulation Symposium, April 1996.
  12. S. Ramsay, J. Nummenmaa, P. Thanisch, R.J. Pooley and S. Gilmore, "Interactive Simulation of Distributed Transaction Processing Commit Protocols", 3rd UK Simulation Conf., April, 1997.
  13. G. Chochia, M.I. Cole, and T. Heywood, "Implementing the Hierarchical PRAM on the 2D Mesh: Analyses and Experiments", Proc. 7th IEEE Symposium on Parallel and Distributed Processing, San Antonio, 1995.
  14. G. Chochia, M.I. Cole, and T. Heywood, "Lower Bounds on Average Time for Random Destination Mesh Routing and Their Utility as Performance Predictors for PRAM Simulation", Proc. First Workshop on Randomized Parallel Computing, at the International Parallel Processing Symposium, Hawaii, 1996.
  15. G. Chochia, "Recursive 3D Mesh Indexing with Improved Locality", to appear in HPCN '97.
  16. G. Chochia, M.I. Cole, and T. Heywood, "Synchronization of Arbitrary Processor Groups in 2-D Dynamically Partitioned Mesh Architectures", University of Edinburgh, Technical Report, ECS-CSG-25-96, 1996.
  17. G. Chochia, M.I. Cole, and T. Heywood, "Experimental Comparison of the H-PRAM and PRAM models", in preparation.

Return to ALAMO page

line

HASE Project
Institute for Computing Systems Architecture, School of Informatics, University of Edinburgh
Last change 3/04/2003


Home : Research : Groups : Hase : Projects : Alamo 

Please contact our webadmin with any comments or changes.
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh.