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

article

Open access

I-structures: data structures for parallel computing

Editor: Susan L. Graham Authors:

Rishiyur S. Nikhil,

Keshav K. PingaliAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 11, Issue 4

Pages 598 - 632

https://doi.org/10.1145/69558.69562

Published: 01 October 1989 Publication History

Abstract

It is difficult to achieve elegance, efficiency, and parallelism simultaneously in functional programs that manipulate large data structures. We demonstrate this through careful analysis of program examples using three common functional data-structuring approaches-lists using Cons, arrays using Update (both fine-grained operators), and arrays using make-array (a “bulk” operator). We then present I-structure as an alternative and show elegant, efficient, and parallel solutions for the program examples in Id, a language with I-structures. The parallelism in Id is made precise by means of an operational semantics for Id as a parallel reduction system. I-structures make the language nonfunctional, but do not lose determinacy. Finally, we show that even in the context of purely functional languages, I-structures are invaluable for implementing functional data abstractions.

References

[1]

ACKERMAN, W.B. A structure memory for data flow computers. Master's thesis and Tech. Rep. TR-186, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, 1978.

[2]

ALLEN, J., AND KENNEDY, K. PFC: A program to convert FORTRAN to parallel form. Tech. Rep. MASC-TR82-6, Rice University, Houston, Tex., March 1982.

[3]

ARIOLA, Z., AND ARVIND. P-TAC: A parallel intermediate language. Tech. Rep. CSG Memo 295, MIT Lab. for Computer Science, Massachusetts ilnstitute of Technology, Cambridge, Jan. 1989.

[4]

ARVIND, AND CULLER, D.E. Dataflow architectures. In Annual Reviews in Computer Science, vol. 1. Annual Reviews Inc., Palo Alto, Calif., 1986, pp. 225-253.

[5]

ARVIND, AND NIKH1L, R.S. Executing a program on the MIT tagged-token datafiow architecture. IEEE Trans. Comput., 1989. To be published. An earlier version appeared in Proceedings of the PARLE Conference (Eindhoven, The Netherlands, June 15-19, 1987). Springer-Verlag LNCS 259, New York, 1987.

[6]

ARVIND, NIKHIL, R. S., AND PINGALI, K.K. Id nouveau reference manual, part II: Semantics. Tech. Rep., Computation Structures Group, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, 1987.

[7]

ARVIND, AND THOMAS, R.E. I-Structures: An efficient data structure for functional languages. Tech. Rep. MIT/LCS/TM-178, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, 1981.

[8]

BARENDREGT, H., AND VAN LEEUWEN, M. Functional programming and the language TALE. Tech. Rep. TR 412, Mathematical Institute, Utrecht, The Netherlands, 1985.

[9]

CULLER, D.E. Effective datafiow execution of scientific applications. Ph.D. dissertation, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge. To appear.

[10]

CULLER, D.E. Resource management for the tagged token datafiow architecture. Tech. Rep. TR-332, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, 1985.

[11]

CULLER, D. E., AND ARVINO. Resource requirements of datafiow programs. In Proceedings of the 15th Annual International Symposium on Computer Architecture (Honolulu, Hawaii, May 1988).

[12]

DRISCOLL, J., SARNAK, N., SLEATOR, D., AND TARJAN, R. Making data structures persistent. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (Berkeley, Calif., May 1986), pp. 109-121.

[13]

GOSTELOW, K. P., AND THOMAS, R.E. A view of datafiow. In AFIPS Conference Proceedings, vol. 48, 1979, pp. 629-636.

[14]

HUDAK, P. A semantic model of reference counting and its abstraction. In Proceedings of the 1986 ACM Conference on Lisp and Functional Programming (Cambridge, Mass., Aug. 1986), pp. 351-363.

[15]

JAOADEESAN, R., PANANOADEN, P., AND PINGALI, K. K. A fully abstract semantics for a functional language with logic variables. In Proceedings of the 4th IEEE Symposium on Logic in Computer Science (Asilomar, Calif., June 5-8, 1989).

[16]

JOHNSSON, T. Lambda lifting: transforming programs to recursive equations. In Proceedings of the Conference on Functional Programming Languages and Computer Architecture (Nancy, France, Sept. 1985). Springer-Verlag LNCS 201, New York, 1985.

[17]

KELLER, R. M. FEL (function equation language) programmer's guide. Tech. Rep., AMPS Tech. Memo. 7, Dept. of Computer Science, University of Utah, Salt Lake City, April 1983.

[18]

KUCK, D. J., KUHN, R., PADUA, D., LEASURE, B., AND WOLFE, M. Dependence graphs and compiler optimizations. In Proceedings of the 8th Annual ACM Symosium on Principles of Programming Languages. ACM, New York, 1981, pp. 207-218.

[19]

LINDSTROM, G. Functional programming and the logic variable. In Proceedings of the 12th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, 1985, pp. 266-280.

[20]

NIKHIL, R.S. Id (version 88.1) reference manual. Tech. Rep. CSG Memo 284, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, Aug. 1988.

[21]

NIKHIL, R. S., PINGALI, K., AND ARVlND. Id nouveau. Tech. Rep. CSG Memo 265, Computation Structures Group, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, July 1986.

[22]

PADUA, D. A., AND WOLFE, M. J. Advanced compiler optimizations for supercomputers. Commun. ACM 29, 12 (Dec. 1986), 1184-1201.

[23]

PEYTON JONES, S. L. The Implementation of Functional Programming Languages. Prentice Hall, Englewood Cliffs, N.J., 1987.

[24]

PINGALI, K. K., AND EKANADHAM, K. Accumulators: New logic variable abstractions for functional languages. In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science. Springer-Verlag LNCS 338, New York, 1988, pp. 377-399.

[25]

TRAUB, K.R. A compiler for the MIT tagged token datafiow architecture. M.S. thesis, Tech. Rep. TR-370, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, Aug. 1986.

[26]

TRAUB, K.R. Sequential implementation of lenient progr ~mming languages. Ph.D. dissertation, Tech. Rep. TR-417, MIT Laboratory for Computer ScierLce, Massachusetts Institute of Technology, Cambridge, May 1988.

[27]

WADLER, P. A new array operation for functional languages. In Proceedings of the Workshop on Graph Reduction (Santa Fe, N. Mex. Sept. 1986). Springer-Verlag LNCS 279, New York, 1986, pp. 328-335.

[28]

WADLER, P. Listlessness is better than laziness: Lazy evaluation and garbage collection at compile time. In Proceedings of the 1984 ACM Con{erence on Lisp and Functional Programming (Austin, Tex., Aug. 1984), pp. 45-52.

Cited By

Westrick SFluet MRainey MAcar U(2024)Automatic Parallelism ManagementProceedings of the ACM on Programming Languages10.1145/36328808:POPL(1118-1149)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632880
Ekaireb TBrand LAvaraddy NMock MKrintz CWolski R(2024)Distributed Dataflow Across the Edge-Cloud Continuum2024 IEEE 17th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD62652.2024.00043(316-327)Online publication date: 7-Jul-2024
https://doi.org/10.1109/CLOUD62652.2024.00043
Ekaireb TBrand LAvaraddy NMock MKrintz CWolski RUstiugov DBruno RFonseca PGrot BBarbalace A(2023)Laminar: Dataflow Programming for Serverless IoT ApplicationsProceedings of the 1st Workshop on SErverless Systems, Applications and MEthodologies10.1145/3592533.3592805(5-11)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3592533.3592805
Show More Cited By

Index Terms

I-structures: data structures for parallel computing

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 11, Issue 4

Oct. 1989

178 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/69558

Editor:
Susan L. Graham

Issue’s Table of Contents

Copyright © 1989 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1989

Published in TOPLAS Volume 11, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

319
Total Citations
View Citations
2,324
Total Downloads

Downloads (Last 12 months)387
Downloads (Last 6 weeks)52

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Westrick SFluet MRainey MAcar U(2024)Automatic Parallelism ManagementProceedings of the ACM on Programming Languages10.1145/36328808:POPL(1118-1149)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632880
Ekaireb TBrand LAvaraddy NMock MKrintz CWolski R(2024)Distributed Dataflow Across the Edge-Cloud Continuum2024 IEEE 17th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD62652.2024.00043(316-327)Online publication date: 7-Jul-2024
https://doi.org/10.1109/CLOUD62652.2024.00043
Ekaireb TBrand LAvaraddy NMock MKrintz CWolski RUstiugov DBruno RFonseca PGrot BBarbalace A(2023)Laminar: Dataflow Programming for Serverless IoT ApplicationsProceedings of the 1st Workshop on SErverless Systems, Applications and MEthodologies10.1145/3592533.3592805(5-11)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3592533.3592805
Arora JWestrick SAcar U(2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591284
Pauloski JHayot-Sasson VWard LHudson NSabino CBaughman MChard KFoster IMohror KArnold DBadia R(2023)Accelerating Communications in Federated Applications with Transparent Object ProxiesProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607047(1-15)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607047
Wilkins MWestrick SKandiah VBernat ASuchy BDeiana ECampanoni SAcar UDinda PHardavellas NDubach CBruening DHardekopf B(2023)WARDen: Specializing Cache Coherence for High-Level Parallel LanguagesProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580013(122-135)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580013
Elakhras ASawhney RGuerrieri AJosipovic LIenne PIenne PZhang Z(2023)Straight to the Queue: Fast Load-Store Queue Allocation in Dataflow CircuitsProceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3543622.3573050(39-45)Online publication date: 12-Feb-2023
https://dl.acm.org/doi/10.1145/3543622.3573050
Mazumdar SScionti AZuckerman SPortero A(2023)NoC-based hardware software co-design framework for dataflow thread managementThe Journal of Supercomputing10.1007/s11227-023-05335-879:16(17983-18020)Online publication date: 11-May-2023
https://dl.acm.org/doi/10.1007/s11227-023-05335-8
Irani SNaor MRubinfeld R(2023)On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?Mathematical Systems Theory10.1007/BF0283583325:2(141-159)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF02835833
Westrick SArora JAcar U(2022)Entanglement detection with near-zero costProceedings of the ACM on Programming Languages10.1145/35476466:ICFP(679-710)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547646
Show More Cited By

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents