This presentation introduces Petalisp, a purely functional array programming language implemented as a library within Common Lisp. The design is predicated on extreme minimalism, utilizing only three core operators—lazy (map), lazy-reshape, and lazy-fuse—while strictly prohibiting control flow and side effects to facilitate automated parallelization.
The core technical achievement lies in the sophisticated compilation pipeline, initiated upon the compute call. This pipeline includes graph assembly, portable type inference via the Typo library (enabling unboxed operations), conversion to a kernel-and-buffer Intermediate Representation (IR), and optimized partitioning algorithms that enforce data locality and generate explicit message passing for multi-core execution without relying on shared memory. Benchmark testing of a Jacobi iteration stencil code demonstrated competitive performance, achieving approximately 16 GigaFLOPS, which significantly exceeds standard Common Lisp implementations and approaches the performance of statically optimized OpenMP C++ code on the test hardware. Future development targets include hierarchical scheduling for distributed computing and open GPU backends (avoiding proprietary APIs like CUDA).
Petalisp: Architecture, Compilation Pipeline, and Performance Analysis
0:07 Core Language Definition: Petalisp is defined as a purely functional array language/library for Common Lisp, designed for automatic parallelization by strictly omitting control flow and side effects.
2:56 Array Shape Generalization: Petalisp generalizes Common Lisp array shapes, defining dimensions via lists of ranges (start, end, step size), allowing for regularly spaced gaps in the index space.
4:19 Core Operator 1: Lazy Map (lazy): Enables element-wise mapping of arbitrary Common Lisp functions over arrays. It supports multiple return values and defers evaluation until the explicit compute function is called.
5:40 Core Operator 2: Lazy Reshape (lazy-reshape): This is the exclusive mechanism for data reordering, achievable through the superposition of six elementary operations: select, broadcast, axis permutation, movement (shifting), scaling, and axis addition/removal (for size one axes).
7:00 Core Operator 3: Fuse (lazy-fuse): Combines multiple non-overlapping lazy arrays into a single composite array, constrained by representability within a single shape.
8:15 Algorithmic Domain: The constrained operator set is sufficient for implementing stencil codes, string processing, interpolation, and complex array operations, including parallel reductions (via repeated pairwise summation and shifting) and matrix multiplication.
11:25 Advanced Capabilities: The architecture allows for the implementation of sorting networks (e.g., Odd-Even merge sort) using the multi-value return capability of lazy-map for pairwise element ordering.
12:35 Performance Benchmarking Context: A Jacobi iteration stencil code was benchmarked on a laptop, establishing a baseline: single-threaded C achieved 6 GFLOPS, and fully optimized OpenMP C++ (static schedule) achieved 24 GFLOPS.
16:13 Benchmark Results: The Petalisp implementation of the Jacobi method achieved 16 GFLOPS, demonstrating competitive performance relative to C++ and substantially outperforming typical Common Lisp performance (1–2 GFLOPS).
18:13 Compilation Pipeline Initiation: The high performance is achieved through a multi-stage optimization and code generation pipeline invoked by the compute function.
19:07 Portable Type Inference (Typo): A key optimization layer utilizes a separate type inference library (Typo) to determine array element types. This enables the specialized use of functions (e.g., specific float additions) and avoids costly boxing/unboxing operations.
20:11 Intermediate Representation (IR): The functional program graph is converted into a bipartite IR structure composed of Kernels (representing nested loops) and Buffers (virtual memory regions).
21:07 Partitioning and Message Passing: Large buffers and kernels are partitioned into shards of equal workload. This algorithm automatically introduces message passing for communication between tasks, thus negating reliance on shared memory synchronization.
21:54 Scheduling Strategy: A modified parallel depth-first scheduler is employed, incorporating optimizations to ensure high temporal cache locality.
22:59 Code Caching: To minimize compilation time, kernels are converted into a minimal, hash-consed blueprint representation (Ukon library) used as a key for an efficient cache lookup, ensuring fast retrieval of optimized compiled code upon repeated invocation.
25:54 Future Development: Near-term goals include publishing the 160-page manual, developing Python bindings, and implementing hierarchical scheduling to enable seamless distributed computing across multiple machines.
26:06 GPU Strategy: The project includes a Cuda prototype but expresses a preference for targeting open APIs like Vulkan or OpenCL rather than proprietary Nvidia toolchains.
28:42 Functional Constraint Implications: The system cannot implement algorithms requiring data inspection for control flow (e.g., pivoting in Gaussian elimination) but forces the adoption of parallelizable alternatives (e.g., conjugate gradient method) where appropriate.