More Web Proxy on the site http://driver.im/

Article

Free access

Alpha du centaur: a prototype environment for the design of parallel regular alorithms

Authors:

Pierrick Gachet,

Christophe Mauras,

Patrice Quinton,

Yannick SaouterAuthors Info & Claims

ICS '89: Proceedings of the 3rd international conference on Supercomputing

Pages 235 - 243

https://doi.org/10.1145/318789.318815

Published: 01 June 1989 Publication History

Abstract

We describe Alpha du Centaur (ADC), a prototype environment for the design of parallel regular algorithms. In ADC, a program is specified using the Alpha language, using system of parameterized linear recurrence equations. The goal of ADC is to make it possible to transform the initial specifications into a parallel algorithm, that is to say, another system of recurrence equations, in which the time and the space index are separated.

The first section of the paper is devoted to a presentation of the model underlying ADC, i.e., system of recurrence equations. The second section summarizes briefly the knowledge we have on this formalism, and presents some open problems. In the third section, we describe the architecture of ADC, which is based on the CENTAUR environment, and we present an example of utilization of ADC for designing a simple algorithm.

References

[1]

E.A. Ashcroft and W.W. Wedge. LUCID: a non procedural language with iteration. CACM, 20(7), July 1977.

Digital Library

[2]

P. Borras, D. Cldment, Th. Despeyroux, J. inccrpi, G. Kahn, B. Lang, and V. Pascual. CENTAUR: the System. Technical Report 777, INRIA, December 1987.

[3]

P.R. Cappello and K. Stciglitz. Unifying VLSI array design with linear transformations of spacetime. In F.P. Preparata, editor, Advances in Cornpuling Research, JAI Press Inc., Grcenwich, U.K., 1984.

[4]

P. Caspi, D. Pilaud, N. Ilalbwachs, and J.A. Plaice. LUSTRE: a declarative language for programming synchronous systems. Ill Fourteenth Annual A CM Syrup. oa Principles of Programming Languages, pages 178-188, ACM, Munich (West Germany), January 1987.

Digital Library

[5]

M.C. Chen. Space-Time Algorithms Semantics and Methodology. PhD thesis, California Institute of Technology, Pasadena, California, May 1983.

Digital Library

[6]

M.C. Chcn. Transformations of Parallel Programs in Crystal. Technical Report YALEU/DCS/RR- 469, Yale University, April 1986.

[7]

J.M. Delosme and I.C.F. Ipsen. "An illustration of a methodology for the construction of efficient systolic architectures i:n V/,Si," Proc. Second Int. Symposium on VLSI technology, systems and applications, Taipci, Taiwan, Mat 1985, 268-273.

[8]

J.M. Delosmc and I.C.F. Ipsen. Efficient systolic arrays for the solution of Toeplitz systems: an illustration of a methodology for the construction of systolic architectures in VLSI, Rapport de recherche YALEU/DCS/RR-341, Department of Computer Science, Yale University, U.S.A., Juin 1985.

[9]

J.M. Delosme and I.C.F. Ipsen. Systolic array synthesis' COlnputability and time cones. In Parallel Algorithms and Architectures, pages 295-312, North-Holland, 1986.

Digital Library

[10]

V. Van Dongen. PRESAGE, a tool for the design of low-cost systolic circuits. In IEEE International Symposium on Circuits and Systems, Espoo, Finland, June 7-9 1988.

[11]

V. Van Dongen and P. Quinton. Uniformization of linear recurrcncc equations: a step towards the automatic synthesis of systolic arrays. In halernational Conference on Systolic Arrays, San Diego (EU), Mat 1988.

[12]

F. Fernandez and P. Quinton. Extension of Chernikova's Algorithm for Solving General Mixed Linear Programming Problems. Technical Report, IRISA- Renncs (France), 1988.

[13]

J.A.B. Fortes and D.I. Moldovan. Data broad~ casting in linearly scheduled array processors. In Proc. lllh Annual Syrup. on Computer Architecture, pages 224-231, 1984.

Digital Library

[14]

M.J. Foster and H.T. Kung. "Tile design of specialpurpose VLSI chips," Computer 13, I (1980), 26- 40.

Digital Library

[15]

P. Frison, P. Cachet, and P. Quinton. Designing systolic arrays with DIASTOL. In S.Y. Kung, R.E. Owcn, and J.G. Nash, editors, VLS{ Signal Processing li, pages 93-105, IEEE Press, November 1986.

[16]

P. Cachet, B. Joinnault, and P. Quinton. Synthesizing systolic arrays using DIASTOL. In W. Moore, A. McCabe, and R. Urquhart, editors, International Workshop on Systolic Arrays, pages 25-36, Adam Hilgcr, University of Oxford, UK, July 2-4 1986.

[17]

N. IIalbwachs, A. Longdlamp, and D. Pilaud. Describing and designing circuits by means of a synchronous declarative language, in From tlDL Description to Guaranteed Correct Circuit Designs, Proceedings of IFIP Working Conference, Grenoble (France), North-Ilolland, 1986.

[18]

N. IIalbwachs and D. Pilaud. Use of real-time declarative language for systolic array design and simulation. In W. Moore, A. McCabe, and R. Urquhart, editors, International Workshop on Systolic Arrays, pages 81-90, Adam Hilger, University of Oxford, UK, July 2-4 1986.

[19]

K. Jainandunsing. Optimal partitioning schemes for wavefront/systolic array processors. IEEE Trans. on Computers, XX(Y):gd0-943, 1986.

[20]

B. Joinnault. Conception d'Mgorithmes et d'architectures systoliques. ThSse de l'Universit6 de Rennes I, Sept 1987.

[21]

G. Kahn. Natural semantics. In STAGS 1987, Springer-Vcrlag, March 1987.

Digital Library

[22]

R.M. Karp, R.E. Miller, and S. Winograd. Tile organizat, ion of computations for uniform recurrence equations. Journal of the Association for Computing Machinery, 14(3):563-590, July 1967.

Digital Library

[23]

H.T. Kung. Why systolic architectures? Computer, 15(1):37-46, January 1982.

Digital Library

[24]

H.T. Kung and C.E. Leiserson. "Systolic arrays for (VLSI)", in {3al chapitre 8.3.

[25]

H.T. Kung and C.E. Leiscrson. Systolic arrays (for VLSI). In Sparse Matrix Proc. 1978, pages 256- 282, Society for Industrial and Applied Mathematics, 1978.

[26]

S.Y. Kung. VLSI Array Processors. Prentice IIall, 1988.

Digital Library

[27]

L. Lamport. Tile parallel execution of Do-Loops. Comm. ACM, 83-93, Fcb. 1983.

Digital Library

[28]

P. LcGucrnic, A. Bcnvcnistc, P. Bournai, and T. Gautier. SIGNAL: a data flow oricntcd language for signal processing. In IEEE Workshop on VLS{, 1984.

[29]

C.E. Lciscrson, F.M. Rose, and J.B. Saxc. Optimizing synchronous circuitry by retiming (preliminary version). In R. Bryant, editor, Proc. 3d Callech Conf on VL$I, pages 87-116, Computer Scicncc Press, 1983.

[30]

C. Lcngauer. Toward Systolizing Compilation: an Overview. Technical Report TR-88-37, Departmeut of Computer Scicncc, The University of Tcxas at Austin, October 1988.

Digital Library

[31]

P.S. Lewis and S.Y. Kung. Dependence graph bascd design of systolic arrays for the algebraic path problem, Proc. 20-1h Asilomar Conference, 10-12 Novcmbrc 1986.

[32]

B. Louka and M. Tchuentc. Dynamic programming on two-dimcnsional systolic arrays. Di.formation Processing Letters, 29, September 1988.

Digital Library

[33]

C.A. Mead and L.A. Conway. Introduction to VLSI systems, Addison-Wcslcy, Reading, Mass., USA, 1980.

Digital Library

[34]

W.L. Miranker and A. Winklcr. "Space-time rcprcscntations of systolic computational structures," Computing 32 (1984), 93-114.

Digital Library

[35]

D.I. Moldovan. On the anMysis and synthesis of VLSI algorithms. IEEE Transactions on Com put. ors, C-31(11), November 1982.

[36]

D.i. Moldovan and J.A.B. Fortcs. Partitioning and mapping algoritltms into fixed size systolic arrays. {EEE Transaction on Colaputers, C-35(1):1- 12, January 1986.

Digital Library

[37]

C. Mongcnet. Unc mdthodc dc conception d'algorithmes systoliques, rdsultats thdoriqucs ct rdalisation. Th~sc de 3icmc cyclc, 1985.

[38]

P. quinton. Mapping recurrences on parallel ardlitectures. In Third International Conference on Supercomputing, Boston (U.S.A), May 1988.

[39]

P. Quinton. The Systematic Design of Systolic Arrays. Technical Report 193, Publication Interne IRISA, Avril 1983.

[40]

P. Quintoa and V. Van Dongcn. The Mapping of Linear Recurrence Equations on Regular Arrays, Submitted to The Jourl~al of VLSI Signal Processing, October 1988

[41]

P. Quinton and P. Gachet. DiASTOL User's Manual- Preliminary Version. Tecllnical Report 233, Publication interne IRISA, Rcnnes, France, Aout 1984.

[42]

S.K. Rao. Regular Iteralive Algorithms and their Implementations on Processor Arrays. PllD thesis, Standford University, U.S.A., October 1985.

Digital Library

[43]

Y. Saouter and P. Quinton. Computabilily of Conditional Recurrence Equations. Technical Report, IR.ISA ~ Rennes (France), 1988.

[44]

A. Schrijver. Theory of Linear and Integer Programming. Wiley.{ntcrscicnce series in Discrete Mathematics, John Wiley and Sons, 1986.

Digital Library

[45]

S.K.Rao. Regular iterative algorithms and their implementations on processor arrays, PhD Thesis, Information Systems laboratory, Sta.ndford University, U.S.A., Octobre 1985.

Digital Library

[46]

Y. Wong and J.M. Delosme. Transformation of Broadcasting into Pipelining. Technical Report, Yale University, Department of Computer Science, June 1987.

Cited By

Bao WKrishnamoorthy SPouchet LRastello FSadayappan P(2016)PolyCheck: dynamic verification of iteration space transformations on affine programsACM SIGPLAN Notices10.1145/2914770.283765651:1(539-554)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2914770.2837656
Bao WKrishnamoorthy SPouchet LRastello FSadayappan PBodik RMajumdar R(2016)PolyCheck: dynamic verification of iteration space transformations on affine programsProceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2837614.2837656(539-554)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2837614.2837656
Cappello P(2008)Application-specific Processor ArchitectureJournal of Signal Processing Systems10.1007/s11265-007-0127-953:1-2(197-215)Online publication date: 1-Nov-2008
https://dl.acm.org/doi/10.1007/s11265-007-0127-9
Show More Cited By

Index Terms

Alpha du centaur: a prototype environment for the design of parallel regular alorithms

Recommendations

A family of NFAs which need 2ⁿ - α deterministic states

We show that for all integers n ≥ 7 and α, such that 5 ≤ α ≤ 2n - 2 and satisfying some coprimality conditions, there exists a minimum n-state nondeterministic finite automaton that is equivalent to a minimum deterministic finite automaton with exactly ...
On $$\alpha $$ź-Domination in Graphs

Let $$G=(V,E)$$G=(V,E) be an isolate-free graph. For some $$\alpha $$ź with $$0<\alpha \le 1$$0<ź≤1, a subset S of V is said to be an $$\alpha $$ź-dominating set if for all $$v \in V {\setminus } S, |N(v)\cap S|\ge \alpha |N(v)|$$vźV\S,|N(v)źS|źź|N(v)|. ...
A High Gain and Low Flicker Noise CMOS Mixer with Low Flicker Noise Corner Frequency Using Tunable Differential Active Inductor

This paper presents the design of a high conversion gain and low flicker noise down conversion CMOS double balanced Gilbert cell mixer using $$0.18\,\upmu \hbox {m}$$ 0.18 μ m CMOS technology. The high conversion gain and low flicker noise mixer is implemented by using a differential ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '89: Proceedings of the 3rd international conference on Supercomputing

June 1989

484 pages

ISBN:0897913094

DOI:10.1145/318789

Chairmen:
George Paul
IBM
,
T. Papatheodorou
CTI, Greese
,
D. Gannon,
E. N. Pudue

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

AICA: Assoc Italianai de Calcolo Automatico
Computer Tech Inst.: Computer Technology Institute
SIGARCH: ACM Special Interest Group on Computer Architecture
SIAM: Society for Industrial and Applied Mathematics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICS89

Sponsor:

AICA
Computer Tech Inst.
SIGARCH
SIAM

ICS89: International Conference on Supercomputing 89

June 5 - 9, 1989

Crete, Greece

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
268
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)11

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bao WKrishnamoorthy SPouchet LRastello FSadayappan P(2016)PolyCheck: dynamic verification of iteration space transformations on affine programsACM SIGPLAN Notices10.1145/2914770.283765651:1(539-554)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2914770.2837656
Bao WKrishnamoorthy SPouchet LRastello FSadayappan PBodik RMajumdar R(2016)PolyCheck: dynamic verification of iteration space transformations on affine programsProceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2837614.2837656(539-554)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2837614.2837656
Cappello P(2008)Application-specific Processor ArchitectureJournal of Signal Processing Systems10.1007/s11265-007-0127-953:1-2(197-215)Online publication date: 1-Nov-2008
https://dl.acm.org/doi/10.1007/s11265-007-0127-9
Kindermann S(2005)Flexible program and architecture specification for massively parallel systemsParallel Processing: CONPAR 94 — VAPP VI10.1007/3-540-58430-7_15(160-171)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-58430-7_15
Verge H(2005)Reduction operators in AlphaPARLE '92 Parallel Architectures and Languages Europe10.1007/3-540-55599-4_101(397-411)Online publication date: 14-Jul-2005
https://doi.org/10.1007/3-540-55599-4_101
Dezan C(1994)Generating Regular Arrays By Program TransformationsProceedings. Second Euromicro Workshop on Parallel and Distributed Processing10.1109/EMPDP.1994.592486(175-179)Online publication date: 1994
https://doi.org/10.1109/EMPDP.1994.592486
Dezan CGautrin EQuinton P(1991)Conception et intégration ďun corrélateur systoliqueDesign and VLSI implementation of a systolic correlatorAnnales des Télécommunications10.1007/BF0299543746:1-2(69-77)Online publication date: Jan-1991
https://doi.org/10.1007/BF02995437
Mauras CQuinton PRajopadhye SSaouter Y(1990)Scheduling affine parameterized recurrences by means of[1990] Proceedings of the International Conference on Application Specific Array Processors10.1109/ASAP.1990.145447(100-110)Online publication date: 1990
https://doi.org/10.1109/ASAP.1990.145447
Quinton PDongen V(1989)The mapping of linear recurrence equations on regular arraysJournal of VLSI Signal Processing Systems10.1007/BF024771761:2(95-113)Online publication date: 1-Oct-1989
https://dl.acm.org/doi/10.1007/BF02477176

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents