| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Application Resource Requirement Estimation in a Parallel-Pipeline Model of Execution
December 2005 (vol. 16 no. 12)
pp. 1154-1165
Abstract—We propose a massively parallel framework termed a parallel-pipeline model of execution that can be employed on a homogeneous computational cluster. We show that speedups near-linear in the number of processors are achievable for applications involving reduction operations based on a novel, parallel-pipeline model of execution. As computational clusters become viable alternative platforms for solving large computational problems, the research community acknowledges that the cluster environment can be used effectively when adaptive resource management is employed. This requires the ability to estimate the resource requirements of applications before scheduling decisions are made. We propose a resource estimation model for applications executed in the parallel-pipeline model of execution. We develop a performance model that predicts the resource utilization (i.e., computation and communication complexity) for applications executing under the parallel-pipeline model on a homogeneous computational cluster. This performance prediction model can provide information to a cluster scheduler.
[1] V. Adve , “Analyzing the Behavior and Performance of Parallel Programs,” PhD thesis, Univ. of Wisconsin-Madison, Dec. 1993.
[2] A. Alexandrov , M.F. Ionescu , K.E. Schauser , and C. Scheiman , “LogGP: Incorporating Long Messages into the LogP Model for Parallel Computation,” J. Parallel and Distributed Computing, vol. 44, no. 1, 1997.
[3] R.H. Bader , M.R. Callahan , D.A. Grim , J.T. Krause , N. Miller , and W.M. Pottenger , “The Role of the $\rm HDDI^{TM}$ Collection Builder in Hierarchical Distributed Dynamic Indexing,” Proc. Textmine '01 Workshop, First SIAM Int'l Conf. Data Mining, Apr. 2001.
[4] N.J. Boden et al., “Myrinet-A Gigabit per Second Local Area Network,” IEEE Micro., vol. 15, 1995.
[5] E. Brill , “A Simple Rule-Based Part of Speech Tagger,” Proc. Third Conf. Applied Natural Language Processing, 1992.
[6] E. Brill , ”A Corpus-Based Approach to Language Learning,“ PhD thesis, Dept. of Computer and Information Science, Univ. of Pennsylvania, 1993.
[7] E. Brill , “Some Advances in Rule-Based Part of Speech Tagging,” Proc. 12th Nat'l Conf. Artificial Intelligence, 1994.
[8] M. Clement and M. Quinn , “Analytical Performance Prediction on Multicomputers,” Supercomputing 93, 1993.
[9] D.E. Culler , R.M. Karp , D.A. Patterson , A. Sahay , E.E. Santos , K.E. Schauser , R. Subramonian , and T. von Eicken , “LogP: A Practical Model of Parallel Computation,” Comm. ACM, vol. 39, no. 11, 1996.
[10] S. Deerwester , S.T. Dumais , G.W. Furnas , T.K. Landauer , and R. Harshman , “Indexing by Latent Semantic Analysis,” J. Am. Soc. for Information Science, vol. 41, no. 6, 1990.
[11] S.T. Dumais , “LSI Meets TREC: A Status Report,” Proc. First Text REtrieval Conf., 1993.
[12] S.T. Dumais , “Latent Semantic Indexing (LSI) and TREC-2,” Proc. Second Text REtrieval Conf., 1994.
[13] S.T. Dumais , “Using LSI for Information Filtering: TREC-3 Experiments,” Proc. Third Text REtrieval Conf., 1995.
[14] H.P. Flatt and K. Kennedy , “Performance of Parallel Processors,” Parallel Computing, vol. 12, no. 1, 1989.
[15] W.N. Francis and H. Kucera , “Brown Corpus Manual,” Dept. of Liguistics, Brown Univ., http://www.hit.uib.no/icame/brownbcm.html , 1979.
[16] P.B. Gibbons , Y. Matias , and V. Ramachandran , “Can A Shared-Memory Model Serve as a Bridging Model for Parallel Computation?” Proc. Ninth ACM Symp. Parallel Algorithms and Architectures, 1997.
[17] J.F. JaJa and K.W. Ryu , “The Black Distributed Memory Model,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 8, 1996.
[18] S.C. Kim and S. Lee , “Measurement and Prediction of Communication Delays in Myrinet Networks,” J. Parallel and Distributed Computing, vol. 61, 2001.
[19] L. Kleinrock , “On the Modeling and Analysis of Computer Networks,” Proc. IEEE, vol. 81, no. 8, 1993.
[20] A. Kontostathis and W.M. Pottenger , “Assessing the Impact of Sparsification on LSI Performance,” Proc. 2004 Grace Hopper Celebration of Women in Computing Conf., 2004.
[21] J. Kuntraruk and W.M. Pottenger , “Massively Parallel Distributed Feature Extraction in Textual Data Mining Using $\rm HDDI^{TM}$ ,” Proc. 10th IEEE Int'l Symp. High Performance Distributed Computing, Aug. 2001.
[22] J. Kuntraruk , “Application Resource Requirement Estimation in a Parallel-Pipeline Model of Execution on a Computation Grid,” PhD thesis, Dept. of Computer Science and Eng., Lehigh Univ., 2003.
[23] V. Mak , “Predicting Performance of Parallel Computations,” IEEE Trans. Parallel Distributed Systems, vol. 1, no. 3, July 1990.
[24] M.M. Mathis , D.J. Kerbyson , and A. Hoisie , “A Performance Model of Non-Deterministic Particle Transport on Large-Scale Systems,” Proc. Int'l Conf. Computational Science, vol. 2659, 2003.
[25] A. Menasce and L. Barroso , “A Methodology for Performance Evaluation of Parallel Applications on Multiprocessors,” J. Parallel Distributed Computing, vol. 14, no. 2, 1992.
[26] J. Mohan , “Performance of Parallel Programs: Models and Analyses,” PhD thesis, Carnegie Mellon Univ., July 1984.
[27] D.A. Patterson and J.L. Hennessy , Computer Architecture: A Quantitative Approach. Morgan-Kaufmann, 1996.
[28] W.M. Pottenger , “The Role of Associativity and Commutativity in the Detection and Transformation of Loop-Level Parallelism,” Proc. 12th ACM Int'l Conf. Supercomputing, July 1998.
[29] W.M. Pottenger , “Theory, Techniques, and Experiments in Solving Recurrences in Computer Programs,” PhD thesis, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, May 1997.
[30] W.M. Pottenger , Y. Kim , and D.D. Meling , Data Mining for Scientific and Engineering Applications, chapter HDDI: Hierarchical Distributed Dynamic Indexing. Kluwer Academic, 2001.
[31] J. Schopf , “Structural Prediction Models for High-Performance Distributed Applications,” Proc. Cluster Computing Conf. 97, 1997.
[32] L.E. Silva and R. Buyya , High Performance Cluster Computing: Programming and Applications, vol. 2, chapter Parallel Programming Models and Paradigms. Prentice Hall, 1999.
[33] IA-32 Linux Supercluster, http://www.ncsa.uiuc.edu/UserInfo/Resources/ HardwareXeonCluster, 2005.
[34] L.G. Valiant , “A Bridging Model for Parallel Computation,” Comm. ACM, vol. 33, no. 8, 1990.
[35] S. Zelikovitz and H. Hirsh , “Using LSI for Text Classification in the Presence of Background Text,” Proc. 10th ACM Int'l Conf. Information and Knowledge Management, 2001.
Index Terms:
Performance analysis, distributed application, measurement and modeling of multiple-processor systems.
Citation:
Jirada Kuntraruk, William M. Pottenger, Andrew M. Ross, "Application Resource Requirement Estimation in a Parallel-Pipeline Model of Execution," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 12, pp. 1154-1165, Dec. 2005, doi:10.1109/TPDS.2005.143
