Brief announcement
| Autor: | Jim Sukha, Kunal Agrawal, I-Ting Angelina Lee |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Software_OPERATINGSYSTEMS
Speedup Spacetime Computer science 020207 software engineering 0102 computer and information sciences 02 engineering and technology Parallel computing Software_PROGRAMMINGTECHNIQUES Cilk Serial code 01 natural sciences Scheduling (computing) Runtime system 010201 computation theory & mathematics Work stealing 0202 electrical engineering electronic engineering information engineering Completion time computer computer.programming_language |
| Zdroj: | SPAA |
| DOI: | 10.1145/1810479.1810517 |
| Popis: | In dynamically multithreaded platforms that employ work stealing, there appears to be a fundamental tradeoff between providing provably good time and space bounds and supporting SP-reciprocity, the property of allowing arbitrary calling between parallel and serial code, including legacy serial binaries. Many known dynamically multithreaded platforms either fail to support SP-reciprocity or sacrifice on the provable time and space bounds that an efficient work-stealing scheduler could otherwise guarantee.We describe PR-Cilk, a design of a runtime system that supports SP-reciprocity in PR-Cilk and provides provable bounds on time and space. In order to maintain the space bound, PR-Cilk uses subtree-restricted work stealing. We show that with subtree-restricted work stealing, PR-Cilk provides the same guarantee on stack space usage as ordinary Cilk. The completion time guaranteed by PR-Cilk is slightly worse than ordinary Cilk. Nevertheless, if the number of times a C function calls a Cilk function is small, or if each Cilk function called by a C function is sufficiently parallel, PR-Cilk still guarantees linear speedup. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|