Jeffrey Bosboom's Blog

[blog] [projects] [about]

Papers: XJava

XJava is a Java language extension for stream programming (pipeline and task parallelism). The authors apparently think in terms of least publishable units, as the language extensions, compiler and runtime, and performance heuristics are each described in a separate paper.

High-Level Multicore Programming with XJava (Frank Otto, Victor Pankratius, Walter F. Tichy; PDF, gratis PDF (requires Google Scholar referrer))

Tasks are special methods with input and output ports, defined with syntax such as public T => U foo() {/* code */}. Periodic tasks have an inner work(T) method that is called for every input item; output is by push u; statements inside the work method. Periodic tasks are equivalent to StreamIt’s filters, except with a fixed input data rate of 1 (per work invocation) and no output rates.

Nonperiodic tasks don’t have work methods; instead they contain calls to other tasks connected by the ||| parallel operator and the => pipelining operator (thus they are the equivalent of StreamIt’s splitjoins and pipelines). The => operator distributes items to a parallel construct in round-robin order (StreamIt’s split roundrobin;), =>* duplicates items to each successor task (StreamIt’s split duplicate;), and =>? distributes items nondeterministically (StreamIt is statically scheduled, so has no equivalent).

Tasks are desugared to Java classes; task calls instantiate those classes and pass them to a thread pool for execution. Periodic tasks are (in this paper) executed in a round-robin fashion as long as they have work; non-periodic tasks (which create new periodic tasks) are executed in parallel if threads are idle or serially otherwise.

Thread pool size, scheduling strategy, pipeline fusion, horizontal fusion (by not expanding periodic tasks), data-parallelization of replicable (stateless) tasks, and task granularity (items processed per execution) are exposed as tunable parameters. Fixed heuristics are presented, e.g., using a thread pool size of 1.5 threads per core, or using a fork-join scheduling strategy for parallel tasks and longest-queue-first for pipelined tasks. These heuristics are shown to be nearly as performant as exhaustive search on the (small) space.

My thoughts

XJava is basically StreamIt in Java but without static data rates or static scheduling. On one hand, XJava can express applications with large amounts of dynamism via dynamic load balancing. On the other hand, it must dynamically dispatch tasks using a thread pool, incurring switching and synchronization costs and inhibiting the underlying JVM JIT’s optimizations, whereas StreamIt schedules tasks completely statically. For example, XJava profits from oversubscribing cores by a factor of 1.5 (presumably because some threads are blocked synchronizing or bringing code or data back into cache), whereas StreamIt has no reason to oversubscribe.

The (syntactic) language extensions seem like a poor tradeoff: they require the use of a separate compiler for no significant gain.