Applying scheduling and tuning to on-line parallel tomography

ABSTRACT

Tomography is a popular technique to reconstruct the three-dimensional structure of an object from a series of two-dimensional projections. Tomography is resource-intensive and deployment of a parallel implementation onto Computational Grid platforms has been studied in previous work. In this work, we address on-line execution of the application where computation is performed as data is collected from an on-line instrument. The goal is to compute incremental 3-D reconstructions that provide quasi-real-time feedback to the user.We model on-line parallel tomography as a tunable application: trade-offs between resolution of the reconstruction and frequency of feedback can be used to accommodate various resource availabilities. We demonstrate that application scheduling/tuning can be framed as multiple constrained optimization problems and evaluate our methodology in simulation. Our results show that prediction of dynamic network performance is key to efficient scheduling and that tunability allows for production runs of on-line parallel tomography in Computational Grid environments.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. C. Kak and M. Slaney. Principles of Computerized Tomography Imaging. IEEE Press, 1998.
	2	G.A. Perkins, C.W. Renken, S.J. Young, S.P. Lamont, M.E. Martone, S. Lindsey, T.G. Frey, and M.H. Ellisman. Electron tomography of large multicomponent biological structures. J. Struct.Biol., 120:219-227, 1997.
	3	J. Frank and M. Radermacher. Three-Dimensional Reconstruction of Nonperiodic Macromolecular Assemblies from Electron Micrographs. In J. K. Koehler, editor, Advanced Techniques in Biological Electron Microscopy III. Springer-Verlag, 1986.
	4	Shava Smallen , Walfredo Cirne , Francine Berman , Steve Young , Mark Ellisman , Jaime Frey , Rich Wolski , Mei-Hui Su , Carl Kesselman, Combining Workstations and Supercomputers to Support Grid Applications: The Parallel Tomography Experience, Proceedings of the 9th Heterogeneous Computing Workshop, p.241, May 01-01, 2000
	5	Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	6	I. Foster, C. Kesselman, and S. Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. To be published in Intl. J. Supercomputer Applications, 2001.
	7	Fangzhe Chang , Vijay Karamcheti , Zvi Kedem, Exploiting application tunability for efficient, predictable resource management in parallel and distributed systems, Journal of Parallel and Distributed Computing, v.60 n.11, p.1420-1445, Nov. 2000 [doi>10.1006/jpdc.2000.1660]
	8	Francine D. Berman , Rich Wolski , Silvia Figueira , Jennifer Schopf , Gary Shao, Application-level scheduling on distributed heterogeneous networks, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.39-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369109]
	9	F. Berman and R. Wolski. The AppLeS Project: A Status Report. In Proc. of the 8th NEC Research Symposium, Berlin, Germany, May 1997.
	10	M. Radermacher. Three-dimensional reconstruction of single particles from random and nonrandom tilt series. J. Electron Microsc. Tech., 9:359-394, 1988.
	11	R. Gordon, R. Bender, and G.T. Herman. Algebraic Reconstruction Techniques (ART) for Three-dimensional Electron Microscopy and X-ray Photography. J. Theoret. Biol., 29:471-481, 1970.
	12	P. Gilbert. Iterative Methods for the Three-dimensional Reconstruction of an Object from Projections. J. Theoret. Biol., 36:105-117, 1972.
	13	I. Foster , C. Kesselman, The Globus Project: A Status Report, Proceedings of the Seventh Heterogeneous Computing Workshop, p.4, March 30-30, 1998
	14	Andrew Grimshaw , Adam Ferrari , Frederick Knabe , Marty Humphrey, Wide-Area Computing: Resource Sharing on a Large Scale, Computer, v.32 n.5, p.29-37, May 1999 [doi>10.1109/2.762790]
	15	M. J. Litzkow, M. Livny, and M. W. Mutka. Condor---A Hunter of Idle Workstations. In Proc. of the 8th Int'l Conf. on Distributed Computing Systems, pages 104-111, 1988.
	16	Henri Casanova , Jack Dongarra, NetSolve: a network server for solving computational science problems, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.40-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369111]
	17	S. Sekiguchi, M. Sato, H. Nakada, S. Matsuoka, and U. Nagashima. Ninf: Network based Information Library for Globally High Performance Computing. In Proc. of Parallel Object-Oriented Methods and Applications (POOMA), pages 39-48, February 1996.
	18	Alan Su , Francine Berman , Richard Wolski , Michelle Mills Strout, Using Apples to Schedule Simple SARA on the Computational Grid, International Journal of High Performance Computing Applications, v.13 n.3, p.253-262, August 1999 [doi>10.1177/109434209901300308]
	19	Neil Spring , Rich Wolski, Application level scheduling of gene sequence comparison on metacomputers, Proceedings of the 12th international conference on Supercomputing, p.141-148, July 1998, Melbourne, Australia [doi>10.1145/277830.277860]
	20	Holly Dail , Graziano Obertelli , Francine Berman , Rich Wolski , Andrew Grimshaw, Application-Aware Scheduling of a Magnetohydrodynamics Application in the Legion Metasystem, Proceedings of the 9th Heterogeneous Computing Workshop, p.216, May 01-01, 2000
	21	Torben Hagerup, Allocating independent tasks to parallel processors: an experimental study, Journal of Parallel and Distributed Computing, v.47 n.2, p.185-197, Dec. 15, 1997 [doi>10.1006/jpdc.1997.1411]
	22	Gabriel E. Soto, Stephen J. Young, Maryann E. Martone, Thomas J. Deerinck, Stephan Lamont, Bridget O. Carragher, Kiyoshi Hamma, and Mark H. Ellisman. Serial section electron tomography: A method for three-dimensional reconstruction of large structures. Neuroimage, 1:230-243, 1994.
	23	Reinhard Klette , Piero Zamperoni, Handbook of image processing operators, John Wiley & Sons, Inc., New York, NY, 1996
	24	Jane W.S. Liu. Real-Time Systems, chapter 2, pages 26-33. Prentice-Hall, Inc., 2000.
	25	Stefan D. Bruda and Selim G. Akl. Real-Time Computation: A Formal Definition and its Applications. Technical Report 435, Queen's University, 2000.
	26	Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]
	27	Maui Scheduler webpage at http://www.mhpcc.edu/maui.
	28	David E. Culler and Jaswinder Pal Singh. Parallel Computer Architecture, chapter 1, pages 60-61. Morgan Kaufmann Publishers, Inc., 1999.
	29	Andrew S. Tanenbaum. Computer Networks, chapter 1, page 8. Prentice Hall, Inc., Third edition, 1996.
	30	Radia Perlman. Interconnections, chapter 2, page 19. Addison Wesley Longman, Inc., second edition, 2000.
	31	Gary Shao, Fran Berman, and Rich Wolski. Using Effective Network Views to Promote Distributed Application Performance. In Proceedings of the 1999 International Conference on Parallel and Distributed Processing Techniques and Applications, 1999.
	32	Linear Programming FAQ webpage at http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html.
	33	Nonlinear Programming FAQ webpage at http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html.
	34	lp_solve FTP site at ftp://ftp.es.ele.tue.nl/pub/lp_solve.
	35	Dimitri P. Bertsekas. Nonlinear Programming, chapter 1, page 2. Athena Scientific, 1999.
	36	Henri Casanova , Dmitrii Zagorodnov , Francine Berman , Arnaud Legrand, Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, Proceedings of the 9th Heterogeneous Computing Workshop, p.349, May 01-01, 2000
	37	Henri Casanova, Simgrid: A Toolkit for the Simulation of Application Scheduling, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.430, May 15-18, 2001
	38	Henri Casanova , Graziano Obertelli , Francine Berman , Rich Wolski, The AppLeS parameter sweep template: user-level middleware for the grid, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.60-es, November 04-10, 2000, Dallas, Texas, United States
	39	Atsuko Takefusa , Satoshi Matsuoka , Kento Aida , Hidemoto Nakada , Umpei Nagashima, Overview of a Performance Evaluation System for Global Computing Scheduling Algorithms, Proceedings of the The Eighth IEEE International Symposium on High Performance Distributed Computing, p.11, August 03-06, 1999
	40	G. von Laszewski, M-H. Su, J. Insley, I. Foster, J. Bresnahan, C. Kesselman, M. Thiebaux, M. Rivers, S. Wang, B. Tieman, and I. McNulty. Real-Time Analysis, Visualization, and Steering of Tomography Experiments at Photon Sources. In Ninth SIAM Conference on Parallel Processing for Scientific Computing, Apr 1999.
	41	Y. Wang, F. De Carlo, I. Foster, J. Insley, C. Kesselman, O. Lane, G. von Laszewski, D. Mancini, I. McNulty, M-H. Su, and B. Tieman. A quasi-realtime xray microtomography system at the Advanced Photon Source. In Proceedings of SPIE, volume 3772, 1999.
	42	Marek Czernuszenko , Dave Pape , Daniel Sandin , Tom DeFanti , Gregory L. Dawe , Maxine D. Brown, The ImmersaDesk and Infinity Wall projection-based virtual reality displays, ACM SIGGRAPH Computer Graphics, v.31 n.2, p.46-49, May 1997 [doi>10.1145/271283.271303]
	43	Cruz-Neira. C., D. Sandin, and T. DeFanti. Surround-Screen Projection-Based Virtual Reality: The Design and Implementation of the CAVE. ACM Computer Graphics, 27(2):135-142, July 1993.
	44	Peter A. Dinda, Bruce Lowekamp, Loukas Kallivokas, and David R. O'Hallaron. The Case for Prediction-based Best-effort Real-time Systems. Technical Report CMU-CS-98-174, Carnegie Mellon University, 1999.
	45	High Performance Parametric Modeling with Nimrod/G: Killer Application for the Global Grid?, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.520, May 01-05, 2000