×

Orthogonal parallel processing in Vector Pascal. (English) Zbl 1077.68553

Summary: Despite the widespread adoption of parallel operations in contemporary CPU designs, their use has been restricted by a lack of appropriate programming language abstractions and development environments. To fully exploit the SIMD model of computation such operations offer, programmers depend on CPU specific machine code or implementation-dependent libraries.
Here we present Vector Pascal (VP), a language designed to enable the elegant and efficient expression of SIMD algorithms. VP imports into Pascal abstraction mechanisms derived from functional languages, in turn having their origins in APL. In particular, it extends all operators to work on vectors of data. The type system is also extended to handle pixels and dimensional analysis. Code generation is via the ILCG system that allows retargeting to multiple different SIMD instruction sets based on formalised descriptions of the instruction set semantics.

MSC:

68N15 Theory of programming languages

Software:

SETL; NESL; APL; ALGOL 68; Miranda; ISDL
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Harland, D., Rekursivobject-oriented computer architecture (1991), Ellis Horwood: Ellis Horwood Chichester, UK, ISBN: 0-7458-0396-2
[2] Intel. Intel architecture software developers manual, vols. 1, 2. 1999.; Intel. Intel architecture software developers manual, vols. 1, 2. 1999.
[3] Advanced Micro Devices. 3DNow! Technology manual. 1999.; Advanced Micro Devices. 3DNow! Technology manual. 1999.
[4] Peleg, A.; Wilke, S.; Weiser, U., Intel MMX for Multimedia PCs, Comm ACM, 40, 1 (1997)
[5] Intel. Willamette processor software developer’s guide, February, 2000.; Intel. Willamette processor software developer’s guide, February, 2000.
[6] Cheong G, Lam M. An optimizer for multimedia instruction sets. Second SUIF workshop, Stanford University, August 1997.; Cheong G, Lam M. An optimizer for multimedia instruction sets. Second SUIF workshop, Stanford University, August 1997.
[7] Leupers R. Compiler optimization for media processors. EMMSEC 99/Sweden 1999.; Leupers R. Compiler optimization for media processors. EMMSEC 99/Sweden 1999.
[8] Krall, A.; Lelait, S., Compilation techniques for multimedia processors, Int J Parallel Program, 28, 4, 347-361 (2000)
[9] Srereman, N.; Govindarajan, G., A vectorizing compiler for multimedia extensions, Int J Parallel Program, 28, 4, 363-400 (2000)
[10] Chaitin G. Elegant Lisp programs. In: Chaitin, G. editor. The limits of mathematics. Berlin: Springer; 1997, p. 29-56.; Chaitin G. Elegant Lisp programs. In: Chaitin, G. editor. The limits of mathematics. Berlin: Springer; 1997, p. 29-56.
[11] Iverson KE. A programming language. Wiley: New York; 1962. p. 16.; Iverson KE. A programming language. Wiley: New York; 1962. p. 16.
[12] Iverson, K. E., Notation as a tool of thought. Comm ACM, 23, 8, 444-465 (1980)
[13] Iverson, K. E., J introduction and dictionary (1995), Iverson Software Inc. (ISI): Iverson Software Inc. (ISI) Toronto, Ont
[14] Cockshott, P.; Renfrew, K., SIMD programming manual for Linux (2004), Springer: Springer Berlin
[15] Cockshott P. Vector Pascal an array language for multimedia code. Proceedings of APL 2002 Conference, p. 83-91.; Cockshott P. Vector Pascal an array language for multimedia code. Proceedings of APL 2002 Conference, p. 83-91.
[16] Ewing AK, Richardson H, Simpson AD, Kulkarni R. Writing data parallel programs with high performance Fortran. Ver 1.3.1. Edinburgh Parallel Computing Centre.; Ewing AK, Richardson H, Simpson AD, Kulkarni R. Writing data parallel programs with high performance Fortran. Ver 1.3.1. Edinburgh Parallel Computing Centre.
[17] Blelloch GE, NESL; Blelloch GE, NESL
[18] Iverson, K. E., A personal view of APL, IBM Systems, 30, 4 (1991)
[19] Burke C. J User Manual. ISI, 1995.; Burke C. J User Manual. ISI, 1995.
[20] Metcalf, M.; Reid, J., The F programming language (1996), Oxford University Press: Oxford University Press Oxford · Zbl 0852.68010
[21] Cole, M., Algorithmic skeletonsstructured management of parallel computation. Research monographs in parallel and distributed computing (1989), Pitman: Pitman London
[22] Michaelson G, Scaife N, Bristow P, King P. Nested algorithmic skeletons from higher order functions. Parallel Algorithms Appl (Special issue on High Level Models and Languages for Parallel Processing), 2001;16:181-206.; Michaelson G, Scaife N, Bristow P, King P. Nested algorithmic skeletons from higher order functions. Parallel Algorithms Appl (Special issue on High Level Models and Languages for Parallel Processing), 2001;16:181-206. · Zbl 1021.68021
[23] Schwartz, J. T.; Dewar, R. B.K.; Dubinsky, E.; Schonberg, E., Programming with setsan introduction to SETL (1986), Springer: Springer New York · Zbl 0604.68001
[24] Turner D. An overview of MIRANDA. SIGPLAN Not 1986.; Turner D. An overview of MIRANDA. SIGPLAN Not 1986.
[25] van der Meulen, S. G., Algol 68 Might Have Beens, SIGPLAN Not, 12, 6 (1977)
[26] Tannenbaum, A. S., A tutorial on Algol 68, Computing Surveys, 8, 2, 155-190 (1976) · Zbl 0361.68008
[27] Occam2 Reference Manual (1988), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[28] Johnston D. C++ parallel systems. ECH: Engineering Computing Newsletter, No. 55, Daresbury Laboratory/Rutherford Appleton Laboratory, March 1995, p. 6-7.; Johnston D. C++ parallel systems. ECH: Engineering Computing Newsletter, No. 55, Daresbury Laboratory/Rutherford Appleton Laboratory, March 1995, p. 6-7.
[29] 3L Limited. Parallel C V2.2, Software Product Description, 1995.; 3L Limited. Parallel C V2.2, Software Product Description, 1995.
[30] Strachey, C., Fundamental concepts of programming languages (1967), University of Oxford: University of Oxford Oxford
[31] Jensen, K.; Wirth, N., Pascal user manual and report (1978), Springer: Springer Berlin · Zbl 0288.68043
[32] ISO. Extended Pascal ISO 10206:1990. 1991.; ISO. Extended Pascal ISO 10206:1990. 1991.
[33] Cockshott P. Direct compilation of high level languages for multi-media instruction-sets, TR2000-72. Department of Computer Science, University of Glasgow, 2000.; Cockshott P. Direct compilation of high level languages for multi-media instruction-sets, TR2000-72. Department of Computer Science, University of Glasgow, 2000.
[34] Susan, L. G., Table driven code generation. IEEE Comput, 13, 8, 25-37 (1980)
[35] Larsen S, Amarasinghe S. Exploiting superword level parallelism with multimedia instruction sets. ACM Conference Programming language design and implementation, Vancouver, 2000, p. 145-56.; Larsen S, Amarasinghe S. Exploiting superword level parallelism with multimedia instruction sets. ACM Conference Programming language design and implementation, Vancouver, 2000, p. 145-56.
[36] Leupers R, Niemmann R, Marwedel P. Methods for retargetable DSP Code Generation, VLSI Signal Processing 94. New York: IEEE, 1994.; Leupers R, Niemmann R, Marwedel P. Methods for retargetable DSP Code Generation, VLSI Signal Processing 94. New York: IEEE, 1994.
[37] Hadjiyiannis G, Hanono S, Devadas S. ISDL: an instruction set description language for retargetability, DAC’97. New York: ACM, 1997.; Hadjiyiannis G, Hanono S, Devadas S. ISDL: an instruction set description language for retargetability, DAC’97. New York: ACM, 1997. · Zbl 1030.68684
[38] Ramsey, N.; Fernandez, M., Specifying representations of machine instructions, ACM Trans Program Languages Systems, 19, 3, 492-524 (1997)
[39] Watt, D. A.; Brown, D. F., Programming language processors in Java (2000), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[40] Aho, A. V.; Ganapathi, M.; TJiang, S. W.K., Code generation using tree matching and dynamic programming, ACM Trans Program Languages Systems, 11, 4, 491-516 (1989)
[41] Cattell, R. G.G., Automatic derivation of code generators from machine descriptions, ACM Trans Program Languages Systems, 2, 2, 173-190 (1980)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.