Franke, Bjoern

Steuwer, Michel

Li, Zhibo

2024-09-18T12:38:26Z

2024-09-18T12:38:26Z

2024-09-18

Modern programming languages provide programmers with rich abstractions for data collections as part of their standard libraries, e.g., Containers in the C++ STL, the Java Collections Framework, or the Scala Collections API. Typically, these collections frameworks are organised as hierarchies that provide programmers with common abstract data types (ADTs) like lists, queues, and stacks. While convenient, this approach introduces problems which ultimately affect application performance due to users overspecifying collection data types limiting implementation flexibility. On the other hand, with the development of parallel computing, there are increasingly parallel architectures that provide parallel speedup for diverse applications such as big data and artificial intelligence, however, there is still a substantial gap between the parallel hardware and writing parallel code. Additionally, the overspecification issue makes it harder for programmers, and particularly non-professional programmers to develop parallel programs. This work develops Collection Skeletons which provide a novel, declarative approach to data collections. Using our framework, programmers explicitly select properties for their collections, thereby truly decoupling specification from implementation. By making collection properties explicit, immediate benefits materialise in the forms of reduced risk of overspecification and increased implementation flexibility. A prototype library of the declarative abstractions for collections is presented in this thesis and shows that benchmark applications rewritten to use Collection Skeletons incur little or no overhead for sequential circumstances. In fact, performance improvements have been reported across most of the 17 benchmarks resulting from the use of Collection Skeletons before trying to parallelize those benchmarks, while also enhancing performance portability across three different hardware platforms. Additionally, by extending the Collection Skeletons towards parallelization, this work shows that Collection Skeletons help shielding the application developer from parallel implementation details, either by encapsulating implicit parallelism or through explicit properties that capture the requirements of parallel algorithmic skeletons. The Collection Skeletons help the programmers write better (parallel) code by providing a property-based declaration for data collections while creating parallel opportunities for library designers who can transparently improve the overall program performance without requiring much effort from the programmers.

https://hdl.handle.net/1842/42187

http://dx.doi.org/10.7488/era/4908

en

The University of Edinburgh

Björn Franke, Zhibo Li, Magnus Morton, and Michel Steuwer. Collection Skeletons: Declarative abstractions for data collections. In Proceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2022, page 189–201, New York, NY, USA, 2022. Association for Computing Machinery

Björn Franke, Zhibo Li, Magnus Morton, and Michel Steuwer. Collection Skeletons: Declarative abstractions for data collections. Under Revision at The Journal of Systems and Software, https://ssrn.com/abstract=4410575, 2024

Collection Skeletons

data collections

parallelization

parallel implementation details

parallel algorithmic skeletons

Collection skeletons: declarative abstractions for data collections

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy