M.Sc Thesis

M.Sc StudentLenchner Israel
SubjectTask-Oriented Programming-Model Exploration
and the ToP-C Program Checker
DepartmentDepartment of Electrical and Computer Engineering
Supervisor ASSOCIATE PROFESSOR Yitzhak Birk


Task-oriented programming (ToP) is a programming model whereby a program comprises a set of serial tasks along with a specification of dependencies among them (Task map). Sometimes there are also Duplicable (multi-instance) tasks: multiple instances may run concurrently on multiple cores (usually different data). If task B depends on A, it may only be dispatched upon A's completion. A task may depend on the return code of another task or upon multiple tasks (e.g., D depends on AND(A,OR(B,C))). This intuitive and convenient model facilitates the expression and discovery of permissible parallelism. Ramon.Space's RC64 chip is a 64-core processor with shared on-chip memory that uses this model. It moreover features a hardware scheduler that can dispatch a runnable task to an available core within a few clock cycles. The extremely fast dispatching enables efficient exploitation of often abundant but useless (due to overhead) fine-grain parallelism. The above makes the intuitive and convenient ToP model both attractive and practical.

While simple and elegant in its pure form, practical ToP instantiations must address issues and needs such as I/O and loops, which complicates matters. Even in the basic model, if a programmer neglects to specify a dependence of task B on task A, the two tasks may be executed in any order, possibly resulting in a Data race and non-deterministic program results.

In this work, we set out to develop a ToP program checker, both as an important tool for ToP programmers and as a vehicle for exploring the model itself. Indeed, we uncovered various subtleties, ambiguities and trade-offs that must be decided in any given instantiation, and propose refinements; E.g., we discuss the case wherein a running task gets a second trigger to start running again. The behavior in such a case must be specified by the model. To this end, we investigate the cause of the retriggering, flesh out relevant definitions and properties, and develop a way to determine whether a task is subject to retriggering.

New algorithms include: Identifying mutually exclusive conditional accesses of two tasks to the same address (may lead to a false race); and efficiently checking for races among members of a set of mutually-independent tasks.

Our insights and algorithms were embodied in ToP-C, a new ToP static program checker. Its input is a ToP program (tasks and tasks’ dependencies). ToP-C's main thrust is detecting data races. Its main components are: 1) determining which pairs of tasks are mutually independent; 2) determining each task's memory footprint; and 3) checking whether any two independent tasks access a common memory address with at least one of them writing to it (Data race). Several important extensions to the ToP model have been proposed, most notably enabling coordinated concurrent execution of multiple Duplicable tasks; ToP-C addresses these extensions, but also has an RC64-specific mode. As such, it is general and forward-looking, yet applicable to an actual product.

In summary, this work both extends the understanding of the ToP model and provides a useful debugging tool.