2010 Poster Sessions : A Buffer-space Efficient and Deadlock-free Scheduling of Stream Applications on Multi-core Architectures

Student Name : Jongsoo Park
Advisor : William Dally
Research Areas: Computer Systems

Stream programming or actor-oriented programming has been extensively studied for embedded applications. One of the main benefits of stream programming is that compilers can statically schedule actors, thereby achieving lower synchronization overhead and buffer-space requirement. Previous stream scheduling algorithms realize this benefit for a certain class of applications, but can suffer exponential buffer space explosion when there is a series of down-sampling actors or encounter a deadlock when there is a feed-back path.

In this poster, we present a stream scheduling algorithm that is buffer-space efficient and deadlock free, while achieving similar synchronization overhead to those of previous algorithms. As opposed to previous algorithms that use the steady state of the entire application as the scheduling unit, our algorithm starts from an initial schedule in which individual actors are scheduling units and refines the initial schedule by selectively aggregating and amortizing actors. Our algorithm appropriately sizes queues associated with each stream, so that the application does not suffer deadlock or serialization from limited queue length. We compare our scheduling algorithm to the latest stream scheduling algorithm, stream graph modulo scheduling (SGMS). Our scheduling algorithm successfully schedules applications that result in excessive buffer space or deadlock with SGMS. For other applications, our algorithm achieves an average of 27% higher throughput than that of SGMS.

Jongsoo Park is a PhD candidate in Electrical Engineering at Stanford University. In Concurrent VLSI Architecture group, he has worked on a compiler framework for ELM architecture and Elk stream programming system. He received his B.S. in Electrical Engineering in Seoul National University. Prior to joining Stanford, Jongsoo worked in Penta Security Systems on its public key cryptography system and in Seoul National University Advanced Compiler Laboratory as a research assistant.