Cited By
View all- Hofmann MRunger G(2008)Towards an adaptive task pool implementation2008 IEEE International Symposium on Parallel and Distributed Processing10.1109/IPDPS.2008.4536477(1-8)Online publication date: Apr-2008
The design and implementation of LilyTask in shared memory
Authors: 
Yan Tang, Tao Wang, Xiaoming LiAuthors Info & Claims
Yan Tang, Tao Wang, Xiaoming LiAuthors Info & ClaimsPages 52 - 63
Abstract
Constructing high performance computing system and providing easy-to-use programming model for users are two main parts of parallel computing, but the latter has been in a sorry state for a long time. LilyTask programming model is based on tasks which can be easily mapped to the decomposition of computation. Without explict synchronization and mutual exclusion, users will concentrate on the inherent parallelism in a problem instead of lock/unlock programming techniques. Most existing implementations of the task pool, a flexible data structure for task parallel, lack basic representation of relations among tasks. LilyTask introduces task group and task relation to help users easily map subproblems to tasks. The kernel of LilyTask system, a distributed task pool, automatically exploits potential parallelism among tasks at runtime. With runtime task assignment and task stealing, LilyTask system achieves dynamic load balancing. Our performance evaluation shows that LilyTask system with task pool outperforms sequential programs and BSPlib in solving both regular and irregular problems.
References
[1]
S. Fortune and J. Wylie. "Parallelism in random access machines," in Proc. the 10th Annual ACM symposium on Theory of Computing, (San Diego, California, United States), pp. 114--118, 1978.
[2]
L. G. Valiant, "A bridging model for parallel computation," Communications of ACM, pp. 103--111, Aug 1990.
[3]
J. M. D. Hill. B. McColl, D. C. Stefanescu, M. W. Goudreau, K. Lang, S. B. Rao, T. Suel, T. Tsantilas, and R. H. Bisseling, "BSPlib: The BSP programming library," Parallel Computing, vol. 24, no. 14, pp. 1947--1980, 1998.
[4]
D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken, "LogP: Towards a realistic model of parallel computation," in Principles Practice of Parallel Programming, pp. 1--12, 1993.
[5]
W. Tao and L. Xiaoming, "Lilytask: A task oriented parallel computation model," in Lecture Notes on Computer Science of Springer. International Workshop on Advanced Parallel Processing Technologies, 2003.
[6]
T. Wang, N. Di, J. Shen, and Y. Tang, "Lilytask programming model and its implementations on smp & cluster," in IASTED International Conference on Parallel and Distributed Computing and Systems, (Marine Del Rey), pp. 301--306, Nov 2003.
[7]
N. Di. T. Wang, and X. Li, "A static task distribute algorithm based on task relation in lilytask," Chinese Journal of Computers, 2005.
[8]
M. Korch and T. Rauber, "Evaluation of task pools for the implementation of parallel irregular algorithms," in Proc. International Conference on Parallel Processing Workshops, (Vancouver, B. C., Canada), pp. 597--606, Aug 2002.
[9]
S. P. Dandamudi and S. Ayachi, "Performance of hierarchical processor scheduling in shared-memory multiprocessor systems," IEEE Transactions on Computers, vol. 48, no. 11, pp. 1202--1213, 1999.
[10]
L. Rudolph, M. Slibkin-Allalouf, and E. Upfal, "A simple load balancing scheme for task allocation in parallel machines," in Proc. the 3rd ACM Symposium on Parallel Algorithms and Architectures, (Hiltion Head, S. C. USA), pp. 237--245, July 1991.
[11]
Y. K. Kwok and I. Ahmad. "Benchmarking and comparison of the task graph scheduling algorithms," Journal of Parallel and Distributed Computing. vol. 59. no. 3, pp. 381--422, 1999.
[12]
T. Johnson, T A. Davis, and S. M. Hadfield, "A concurrent dynamic task graph," Parallel Computing, vol. 22. no. 3, pp. 327--333. 1996.
[13]
S. Ramaswamy, S. Sapatnekar, and P. Banerjee, "A framework for exploiting data and functional parallelism on distributed memory multicomputers," IEEE Transactions on Parallel and Distributed Systems. vol. 8, no. 11, pp. 1098--1116. 1997.
[14]
I. Foster, "Task parallel and high performance languages," IEEE Parallel and Distributed Technology, vol. 2, no. 3, pp. 27--36, 1994.
[15]
H. Bal and M. Haines, "Approaches for integrating task and data parallelism," IEEE Concurrency, vol. 6, no. 3, pp. 74--84, 1998.
Index Terms
- The design and implementation of LilyTask in shared memory
Recommendations
Multigrain shared memory
Parallel workstations, each comprising tens of processors based on shared memory, promise cost-effective scalable multiprocessing. This article explores the coupling of such small- to medium-scale shared-memory multiprocessors through software over a ...
Comments
Information & Contributors
Information
Published In
Copyright © 2005 Authors.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 July 2005
Published in SIGOPS Volume 39, Issue 3
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 205Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
Cited By
View all- Hofmann MRunger G(2008)Towards an adaptive task pool implementation2008 IEEE International Symposium on Parallel and Distributed Processing10.1109/IPDPS.2008.4536477(1-8)Online publication date: Apr-2008
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in