Abstract
The SB-PRAM is a parallel architecture which uses i) multithreading in order to hide latency, ii) a pipelined combining butterfly network in order to reduce hot spots and iii) address hashing in order to randomize network traffic and to reduce memory module congestion. Previous work suggests that such a machine will efficiently simulate shared memory with constant access time independent of the number of processors (i.e. the theoretical PRAM model) provided enough threads can be kept busy. A prototype of a 64 processor SB-PRAM has been completed. We report some technical data about this prototype as well as performance measurements. On all benchmark programs measured so far the performance of the real machine was at most 1,37 % slower than predicted by simulations which assume perfect shared memory with uniform access time.
This work was supported by the German Science Foundation (DFG) under contract SFB 124, TP D4.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Valiant, L.G.: General Purpose Parallel Architectures. In van Leeuwen, J., ed.: Handbook of Theoretical Computer Science, Vol. A. Elsevier Science Publishers and MIT Press (1990) 943–971
Abolhassan, F., Keller, J., Paul, W.J.: On the Cost-Effectiveness of PRAMs. In: Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing. (1991) 2–9
Gottlieb, A., Grishman, R., Kruskal, C.P., McAuliffe, K.P., Rudolph, L., Snir, M.: The NYU Ultracomputer-Designing an MIMD Shared Memory Parallel Computer. In: IEEE Transactions on Computers, C-32(2). (Feb 1983) 175–189
Pfister, G.F., Brantley, W.C., George, D.A., Harvey, S.L., Kleinfelder, W.J., McAuliffe, K.P., Melton, E.A., Norton, V.A., Weiss, J.: The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture. In: International Conference on Parallel Processing, Los Alamitos, Ca., USA, IEEE Computer Society Press (1985) 764–771
Alverson, R., Callahan, D., Cummings, D., Koblenz, B., Porterfield, A., Smith, B.: The Tera computer system. In: Proceedings of the1990 International Conference on Supercomputing. (1990) 1–6
Smith, B.J.: Architecture and applications of the HEP multiprocessor computer system. SPIE Real-Time Signal Processing IV 298 (1981) 241–248
Abolhassan, F., Keller, J., Paul, W.J.: On the Cost-Effectiveness of PRAMs. In: Acta Informatica 36. Springer-Verlag (1999) 463–487
Keller, J., Kessler, C.W., Träff, J.L.: Practical PRAM Programming. Wiley Interscience Series on Parallel and Distributed Computing (2000)
Valiant, L.G.: Bulk-synchronous parallel computers. In: Parallel Processing and Artificial Intelligence. (1989) 15–22
Valiant, L.G.: A Bridging Model for Parallel Computation. In: Communications of the ACM. (August 1990) 103–111
Abolhassan, F.: Vergleich von Parallelen Maschinen mit gemeinsamen und verteilten Speichern. PhD thesis, Universität des Saarlandes, Saarbrücken (1994)
Abolhassan, F., Drefenstedt, R., Keller, J., Paul, W.J., Scheerer, D.: On the Physical Design of PRAMs. In: Computer Journal 1993 36(8). (1993) 756–762
Scheerer, D.: Der Prozessor der SB-PRAM. PhD thesis, Universität des Saarlandes, Saarbrücken (1995)
Keller, J., Paul, W.J., Scheerer, D.: Realization of PRAMs: Processor Design. In: Proc. WDAG’ 94, 8th Int. Workshop on Distributed Algorithms. Springer Lecture Notes in Computer Science No. 857 (1994) 17–27
Göler, T.: Der Sortierknoten der SB-PRAM. Master’s thesis, Universität des Saarlandes, Saarbrücken (1996)
Ranade, A.G.: How to Emulate Shared Memory. In: Journal of Computer and System Sciences 42. (1991) 307–326
Ranade, A.G., Bhatt, S.N., Johnson, S.L.: The Fluent Abstract Machine. In: Proceedings of the 5th MIT Conference on Advanced Research in VLSI, Cambridge, MA, MIT Press (1988) 71–93
Walle, T.: Das Netzwerk der SB-PRAM. PhD thesis, Universität des Saarlandes, Saarbrücken (1997)
Cross, D., Drefenstedt, R., Keller, J.: Reduction of Network Cost and Wiring in Ranade’s Butterfly Routing. In: Information Processing Letters, vol. 45 no. 2. (1993) 63–97
A. Formella, J. Keller, T.W.: HPP-A High Performance PRAM. Volume 2. (1996) 425–434
Bach, P.: Entwurf und Realisierung der Prozessorplatine der SB-PRAM. Master’s thesis, Universität des Saarlandes, Saarbrücken (1996)
Bach, P.: Schnelle Fertigungsfehlersuche am Beispiel der Prozessorplatine CPULIGHT. Dissertation (paul), Universität des Saarlandes, Saarbrücken (2000)
Janocha, S.: Design der PCIPro-Karte. Master’s thesis, Universität des Saarlandes, Saarbrücken (2000)
Lichtenau, C.: Entwurf und Realisierung des Speicherboards der SB-PRAM. Diplomarbeit an der universität des saarlandes fb 14 (paul), Universität des Saarlandes, Saarbrücken (1996)
Lichtenau, C.: Entwurf und Realisierung des Aufbaus und der Testumgebung der SB-PRAM. Dissertation, Universität des Saarlandes, Saarbrücken (2000)
Fischer, J.: Entwurf und Realisierung der Netzwerkplatinen der SB-PRAM. Diplomarbeit an der Universität des Saarlandes FB 14 (paul), Universität des Saarlandes, Saarbrücken (1998)
Keller, J.: Zur Realisierbarkeit des PRAM Modelles. PhD thesis, Universität des Saarlandes, Saarbrücken (1992)
1990, I.S..: Standard test access port and boundary scan architecture. Institute of Electrical and Electronics Engineers (1993)
Bosch, M.: Fehlermodelle und Tests für das Netzwerk der SB-PRAM. Dissertation, Universität des Saarlandes, Saarbrücken (2000)
Kessler, C., Seidl, H.: Fork95 Language and Compiler for the SB-PRAM. In: Proceedings of the 5th International Workshop on Compilers for Parallel Computers. (1995) 408–420
Röhrig, J.: Implementierung der P4-Laufzeitbibliothek auf der SB-PRAM. Master’s thesis, Universität des Saarlandes, Saarbrücken (1996)
Wilson, J.M.: Operating System Data Structures for Shared-Memory MIMD Machines with Fetch-and-Add. PhD thesis, Courant Institute, New York University (1998)
Formella, A., Grün, T., Keller, J., Paul, W., Rauber, T., Rünger, G.: Scientific applications on the sb-pram. In: Proceedings of International Conference on Multi-Scale Phenomena and their Simulation in Parallel, World Scientific (1997)
Lenoski, D., Laudon, J., Joe, T., Nakahira, D., Stevens, L., Gupta, A., Hennessy, J.: The DASH prototype: Logic overhead and performance. IEEE Transactions on Parallel and Distributed Systems 4 (1993) 41–61
Agarwal, A., Bianchini, R., Chaiken, D., Johnson, K., Kranz, D., Kubiatowicz, J., Lim, B.H., Mackenzie, K., Yeung, D.: The MIT Alewife Machine: Architecture and Performance. In: International Symposium on Computer Architecture 1995. (1995)
Dementiev, R., Klein, M., Paul, W.J.: Performance of MP3D on the SB-PRAM prototype. In: Proc. of the Europar’02. (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Paul, W.J., Bach, P., Bosch, M., Fischer, J., Lichtenau, C., Röhrig, J. (2002). Real PRAM Programming. In: Monien, B., Feldmann, R. (eds) Euro-Par 2002 Parallel Processing. Euro-Par 2002. Lecture Notes in Computer Science, vol 2400. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45706-2_71
Download citation
DOI: https://doi.org/10.1007/3-540-45706-2_71
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44049-9
Online ISBN: 978-3-540-45706-0
eBook Packages: Springer Book Archive