Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
Editorial Board Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos New York University, NY, USA Doug Tygar University of California, Berkeley, CA, USA Moshe Y. Vardi Rice University, Houston, TX, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany
3038
Springer Berlin Heidelberg New York Hong Kong London Milan Paris Tokyo
Marian Bubak Geert Dick van Albada Peter M.A. Sloot Jack J. Dongarra (Eds.)
Computational Science - ICCS 2004 4th International Conference Kraków, Poland, June 6-9, 2004 Proceedings, Part III
Springer
eBook ISBN: Print ISBN:
3-540-24688-6 3-540-22116-6
©2005 Springer Science + Business Media, Inc.
Print ©2004 Springer-Verlag Berlin Heidelberg All rights reserved
No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher
Created in the United States of America
Visit Springer's eBookstore at: and the Springer Global Website Online at:
http://ebooks.springerlink.com http://www.springeronline.com
Preface
The International Conference on Computational Science (ICCS 2004) held in Kraków, Poland, June 6–9, 2004, was a follow-up to the highly successful ICCS 2003 held at two locations, in Melbourne, Australia and St. Petersburg, Russia; ICCS 2002 in Amsterdam, The Netherlands; and ICCS 2001 in San Francisco, USA. As computational science is still evolving in its quest for subjects of investigation and efficient methods, ICCS 2004 was devised as a forum for scientists from mathematics and computer science, as the basic computing disciplines and application areas, interested in advanced computational methods for physics, chemistry, life sciences, engineering, arts and humanities, as well as computer system vendors and software developers. The main objective of this conference was to discuss problems and solutions in all areas, to identify new issues, to shape future directions of research, and to help users apply various advanced computational techniques. The event harvested recent developments in computational grids and next generation computing systems, tools, advanced numerical methods, data-driven systems, and novel application fields, such as complex systems, finance, econo-physics and population evolution. Keynote lectures were delivered by David Abramson and Alexander V. Bogdanov, From ICCS 2003 to ICCS 2004 – Personal Overview of Recent Advances in Computational Science; Iain Duff, Combining Direct and Iterative Methods for the Solution of Large Sparse Systems in Different Application Areas; Chris Johnson, Computational Multi-field Visualization; John G. Michopoulos, On the Pathology of High Performance Computing; David De Roure, Semantic Grid; and Vaidy Sunderam, True Grid: What Makes a Grid Special and Different? In addition, three invited lectures were delivered by representatives of leading computer system vendors, namely: Frank Baetke from Hewlett Packard, Eng Lim Goh from SGI, and David Harper from the Intel Corporation. Four tutorials extended the program of the conference: and Krzysztof Wilk, Practical Introduction to Grid and Grid Services; Software Engineering Methods for Computational Science; the CrossGrid Tutorial by the CYFRONET CG team; and the Intel tutorial. We would like to thank all keynote, invited and tutorial speakers for their interesting and inspiring talks. Aside of plenary lectures, the conference included 12 parallel oral sessions and 3 poster sessions. Ever since the first meeting in San Francisco, ICCS has attracted an increasing number of more researchers involved in the challenging field of computational science. For ICCS 2004, we received 489 contributions for the main track and 534 contributions for 41 originally-proposed workshops. Of these submissions, 117 were accepted for oral presentations and 117 for posters in the main track, while 328 papers were accepted for presentations at 30 workshops. This selection was possible thanks to the hard work of the Program
VI
Preface
Committee members and 477 reviewers. The author index contains 1395 names, and almost 560 persons from 44 countries and all continents attended the conference: 337 participants from Europe, 129 from Asia, 62 from North America, 13 from South America, 11 from Australia, and 2 from Africa. The ICCS 2004 proceedings consists of four volumes, the first two volumes, LNCS 3036 and 3037 contain the contributions presented in the main track, while volumes 3038 and 3039 contain the papers accepted for the workshops. Parts I and III are mostly related to pure computer science, while Parts II and IV are related to various computational research areas. For the first time, the ICCS proceedings are also available on CD. We would like to thank Springer-Verlag for their fruitful collaboration. During the conference the best papers from the main track and workshops as well as the best posters were nominated and presented on the ICCS 2004 Website. We hope that the ICCS 2004 proceedings will serve as a major intellectual resource for computational science researchers, pushing back the boundaries of this field. A number of papers will also be published as special issues of selected journals. We owe thanks to all workshop organizers and members of the Program Committee for their diligent work, which ensured the very high quality of the event. We also wish to specifically acknowledge the collaboration of the following colleagues who organized their workshops for the third time: Nicoletta Del Buono (New Numerical Methods) Andres Iglesias (Computer Graphics), Dieter Kranzlmueller (Tools for Program Development and Analysis), Youngsong Mun (Modeling and Simulation in Supercomputing and Telecommunications). We would like to express our gratitude to Prof. Ryszard Tadeusiewicz, Rector of the AGH University of Science and Technology, as well as to Prof. Marian Noga, Dr. Jan Kulka and for their personal involvement. We are indebted to all the members of the Local Organizing Committee for their enthusiastic work towards the success of ICCS 2004, and to numerous colleagues from ACC CYFRONET AGH and the Institute of Computer Science for their help in editing the proceedings and organizing the event. We very much appreciate the help of the Computer Science and Computational Physics students during the conference. We owe thanks to the ICCS 2004 sponsors: Hewlett-Packard, Intel, IBM, SGI and ATM, SUN Microsystems, Polish Airlines LOT, ACC CYFRONET AGH, the Institute of Computer Science AGH, the Polish Ministry for Scientific Research and Information Technology, and Springer-Verlag for their generous support. We wholeheartedly invite you to once again visit the ICCS 2004 Website (http://www.cyfronet.krakow.pl/iccs2004/), to recall the atmosphere of those June days in Kraków. June 2004
Marian Bubak, Scientific Chair 2004 on behalf of the co-editors: G. Dick van Albada Peter M.A. Sloot Jack J. Dongarra
Organization
ICCS 2004 was organized by the Academic Computer Centre CYFRONET AGH University of Science and Technology (Kraków, Poland) in cooperation with the Institute of Computer Science AGH, the University of Amsterdam (The Netherlands) and the University of Tennessee (USA). All the members of the Local Organizing Committee are the staff members of CYFRONET and/or ICS. The conference took place at the premises of the Faculty of Physics and Nuclear Techniques AGH and at the Institute of Computer Science AGH.
Conference Chairs Scientific Chair – Marian Bubak (Institute of Computer Science and ACC CYFRONET AGH, Poland) Workshop Chair – Dick van Albada (University of Amsterdam, The Netherlands) Overall Chair – Peter M.A. Sloot (University of Amsterdam, The Netherlands) Overall Co-chair – Jack Dongarra (University of Tennessee, USA)
Local Organizing Committee Marian Noga Marian Bubak Zofia Mosurska Maria Stawiarska Mietek Pilipczuk Aleksander Kusznir
Program Committee Jemal Abawajy (Carleton University, Canada) David Abramson (Monash University, Australia) Dick van Albada (University of Amsterdam, The Netherlands) Vassil Alexandrov (University of Reading, UK) Srinivas Aluru (Iowa State University, USA) David A. Bader (University of New Mexico, USA)
VIII
Organization
J.A. Rod Blais (University of Calgary, Canada) Alexander Bogdanov (Institute for High Performance Computing and Information Systems, Russia) Peter Brezany (University of Vienna, Austria) Marian Bubak (Institute of Computer Science and CYFRONET AGH, Poland) Rajkumar Buyya (University of Melbourne, Australia) Bastien Chopard (University of Geneva, Switzerland) Paul Coddington (University of Adelaide, Australia) Toni Cortes (Universitat Politècnica de Catalunya, Spain) Yiannis Cotronis (University of Athens, Greece) Jose C. Cunha (New University of Lisbon, Portugal) Brian D’Auriol (University of Texas at El Paso, USA) Federic Desprez (INRIA, France) Tom Dhaene (University of Antwerp, Belgium) Hassan Diab (American University of Beirut, Lebanon) Beniamino Di Martino (Second University of Naples, Italy) Jack Dongarra (University of Tennessee, USA) Robert A. Evarestov (SPbSU, Russia) Marina Gavrilova (University of Calgary, Canada) Michael Gerndt (Technical University of Munich, Germany) Yuriy Gorbachev (Institute for High Performance Computing and Information Systems, Russia) Andrzej Goscinski (Deakin University, Australia) Ladislav Hluchy (Slovak Academy of Sciences, Slovakia) Alfons Hoekstra (University of Amsterdam, The Netherlands) Hai Jin (Huazhong University of Science and Technology, ROC) Peter Kacsuk (MTA SZTAKI Research Institute, Hungary) Jacek Kitowski (AGH University of Science and Technology, Poland) Dieter Kranzlmüller (Johannes Kepler University Linz, Austria) Domenico Laforenza (Italian National Research Council, Italy) Antonio Lagana (Università di Perugia, Italy) Francis Lau (University of Hong Kong, ROC) Bogdan Lesyng (ICM Warszawa, Poland) Thomas Ludwig (Ruprecht-Karls-Universität Heidelberg, Germany) Emilio Luque (Universitat Autònoma de Barcelona, Spain) Michael Mascagni (Florida State University, USA) Edward Moreno (Euripides Foundation of Marilia, Brazil) Jiri Nedoma (Institute of Computer Science AS CR, Czech Republic) Genri Norman (Russian Academy of Sciences, Russia) Stephan Olariu (Old Dominion University, USA) Salvatore Orlando (University of Venice, Italy) Marcin Paprzycki (Oklahoma State University, USA) Ron Perrott (Queen’s University of Belfast, UK) Richard Ramaroson (ONERA, France) Rosemary Renaut (Arizona State University, USA)
Organization
Alistair Rendell (Australian National University, Australia) Paul Roe (Queensland University of Technology, Australia) Hong Shen (Japan Advanced Institute of Science and Technology, Japan) Dale Shires (U.S. Army Research Laboratory, USA) Peter M.A. Sloot (University of Amsterdam, The Netherlands) Gunther Stuer (University of Antwerp, Belgium) Vaidy Sunderam (Emory University, USA) Boleslaw Szymanski (Rensselaer Polytechnic Institute, USA) Ryszard Tadeusiewicz (AGH University of Science and Technology, Poland) Pavel Tvrdik (Czech Technical University, Czech Republic) Putchong Uthayopas (Kasetsart University, Thailand) Jesus Vigo-Aguiar (University of Salamanca, Spain) Jens Volkert (University of Linz, Austria) Koichi Wada (University of Tsukuba, Japan) Jerzy Wasniewski (Technical University of Denmark, Denmark) Greg Watson (Los Alamos National Laboratory, USA) University of Technology, Poland) Roland Wismüller (LRR-TUM, Germany) Roman Wyrzykowski (Technical University of Poland) Jinchao Xu (Pennsylvania State University, USA) Yong Xue (Chinese Academy of Sciences, ROC) Xiaodong Zhang (College of William and Mary, USA) Alexander Zhmakin (Soft-Impact Ltd, Russia) (Institute of Computer Science and CYFRONET AGH, Poland) Zahari Zlatev (National Environmental Research Institute, Denmark) Albert Zomaya (University of Sydney, Australia) Elena Zudilova (University of Amsterdam, The Netherlands)
Reviewers Abawajy, J.H. Abe, S. Abramson, D. Adali, S. Adcock, M. Adriaansen, T. Ahn, G. Ahn, S.J. Albada, G.D. van Albuquerque, P. Alda, W. Alexandrov, V. Alt, M.
Aluru, S. Anglano, C. Archibald, R. Arenas, A. Astalos, J. Ayani, R. Ayyub, S. Babik, M. Bader, D.A. Bajaj, C. Baker, M. Balk, I.
Balogh, Z. Bang, Y.C. Baraglia, R. Barron, J. Baumgartner, F. Becakaert, P. Belleman, R.G. Bentes, C. Bernardo Filho, O. Beyls, K. Blais, J.A.R. Boada, I. Bode, A.
IX
X
Organization
Bogdanov, A. Bollapragada, R. Boukhanovsky, A. Brandes, T. Brezany, P. Britanak, V. Bronsvoort, W. Brunst, H. Bubak, M. Budinska, I. Buono, N. Del Buyya, R. Cai, W. Cai, Y. Cannataro, M. Carbonell, N. Carle, G. Caron, E. Carothers, C. Castiello, C. Chan, P. Chassin-deKergommeaux, J. Chaudet, C. Chaves, J.C. Chen, L. Chen, Z. Cheng, B. Cheng, X. Cheung, B.W.L. Chin, S. Cho, H. Choi, Y.S. Choo, H.S. Chopard, B. Chuang, J.H. Chung, R. Chung, S.T. Coddington, P. Coeurjolly, D. Congiusta, A. Coppola, M. Corral, A. Cortes, T. Cotronis, Y.
Cramer, H.S.M. Cunha, J.C. Danilowicz, C. D’Auriol, B. Degtyarev, A. Denazis, S. Derntl, M. Desprez, F. Devendeville, L. Dew, R. Dhaene, T. Dhoedt, B. D’Hollander, E. Diab, H. Dokken, T. Dongarra, J. Donnelly, D. Donnelly, W. Dorogovtsev, S. Duda, J. Dudek-Dyduch, E. Dufourd, J.F. Dumitriu, L. Duplaga, M. Dupuis, A. Dzwinel, W. Embrechts, M.J. Emiris, I. Emrich, S.J. Enticott, C. Evangelos, F. Evarestov, R.A. Fagni, T. Faik, J. Fang, W.J. Farin, G. Fernandez, M. Filho, B.O. Fisher-Gewirtzman, D. Floros, E. Fogel, J. Foukia, N. Frankovic, B. Fuehrlinger, K. Funika, W.
Gabriel, E. Gagliardi, F. Galis, A. Galvez, A. Gao, X.S. Garstecki, L. Gatial, E. Gava, F. Gavidia, D.P. Gavras, A. Gavrilova, M. Gelb, A. Gerasimov, V. Gerndt, M. Getov, V. Geusebroek, J.M. Giang, T. Gilbert, M. Glasner, C. Gobbert, M.K. Gonzalez-Vega, L. Gorbachev, Y.E. Goscinski, A.M. Goscinski, W. Gourhant, Y. Gualandris, A. Guo, H. Ha, R. Habala, O. Habib, A. Halada, L. Hawick, K. He, K. Heinzlreiter, P. Heyfitch, V. Hisley, D.M. Hluchy, L. Ho, R.S.C. Ho, T. Hobbs, M. Hoekstra, A. Hoffmann, C. Holena, M. Hong, C.S. Hong, I.
Organization
Hong, S. Horan, P. Hu, S.M. Huh, E.N. Hutchins, M. Huynh, J. Hwang, I.S. Hwang, J. Iacono, M. Iglesias, A. Ingram, D. Jakulin, A. Janciak, I. Janecek, J. Janglova, D. Janicki, A. Jin, H. Jost, G. Juhola, A. Kacsuk, P. Kalousis, A. Kalyanaraman, A. Kang, M.G. Karagiorgos, G. Karaivanova, A. Karl, W. Karypis, G. Katarzyniak, R. Kelley, T. Kelly, W. Kennedy, E. Kereku, E. Kergommeaux, J.C. De Kim, B. Kim, C.H. Kim, D.S. Kim, D.Y. Kim, M. Kim, M.J. Kim, T.W. Kitowski, J. Klein, C. Ko, P. Kokoszka, P. Kolingerova, I.
Kommineni, J. Korczak, J.J. Korkhov, V. Kou, G. Kouniakis, C. Kranzlmüller, D. Krzhizhianovskaya, V.V. Kuo, T.W. Kurka, G. Kurniawan, D. Kurzyniec, D. Laclavik, M. Laforenza, D. Lagan, A. Lagana, A. Lamehamedi, H. Larrabeiti, D. Latt, J. Lau, F. Lee, H.G. Lee, M. Lee, S. Lee, S.S. Lee, S.Y. Lefevre, L. Leone, P. Lesyng, B. Leszczynski, J. Leymann, F. Li,T. Lindner, P. Logan, B. Lopes, G.P. Lorencz, R. Low, M.Y.H. Ludwig, T. Luethi, J. Lukac, R. Luksch, P. Luque, E. Mairandres, M. Malawski, M. Malony, A. Malyshkin, V.E. Maniatty, W.A.
Marconi, S. Mareev, V. Margalef, T. Marrone, S. Martino, B. Di Marzolla, M. Mascagni, M. Mayer, M. Medeiros, P. Meer, H. De Meyer, N. Miller, B. Miyaji, C. Modave, F. Mohr, B. Monterde, J. Moore, S. Moreno, E. Moscato, F. Mourelle, L.M. Mueller, M.S. Mun, Y. Na, W.S. Nagel, W.E. Nanni, M. Narayanan, M. Nasri, A. Nau, B. Nedjah, N. Nedoma, J. Negoita, C. Neumann, L. Nguyen, G.T. Nguyen, N.T. Norman, G. Olariu, S. Orlando, S. Orley, S. Otero, C. Owen, J. Palus, H. Paprzycki, M. Park, N.J. Patten, C. Peachey, T.C.
XI
XII
Organization
Peluso, R. Peng,Y. Perales, F. Perrott, R. Petit, F. Petit, G.H. Pfluger, P. Philippe, L. Platen, E. Plemenos, D. Pllana, S. Polak, M. Polak, N. Politi, T. Pooley, D. Popov, E.V. Puppin, D. Qut, P.R. Rachev, S. Rajko, S. Rak, M. Ramaroson, R. Ras, I. Rathmayer, S. Raz, D. Recio, T. Reichel, L. Renaut, R. Rendell, A. Richta, K. Robert, Y. Rodgers, G. Rodionov, A.S. Roe, P. Ronsse, M. Ruder, K.S. Ruede, U. Rycerz, K. Sanchez-Reyes, J. Sarfraz, M. Sbert, M. Scarpa, M. Schabanel, N. Scharf, E. Scharinger, J.
Schaubschlaeger, C. Schmidt, A. Scholz, S.B. Schreiber, A. Seal, S.K. Seinstra, F.J. Seron, F. Serrat, J. Shamonin, D.P. Sheldon, F. Shen, H. Shende, S. Shentu, Z. Shi, Y. Shin, H.Y. Shires, D. Shoshmina, I. Shrikhande, N. Silvestri, C. Silvestri, F. Simeoni, M. Simo, B. Simonov, N. Siu, P. Slizik, P. Slominski, L. Sloot, P.M.A. Slota, R. Smetek, M. Smith, G. Smolka, B. Sneeuw, N. Snoek, C. Sobaniec, C. Sobecki, J. Sofroniou, M. Sole, R. Soofi, M. Sosnov, A. Sourin, A. Spaletta, G. Spiegl, E. Stapor, K. Stuer, G. Suarez Rivero, J.P.
Sunderam, V. Suzuki, H. Szatzschneider, W. Szczepanski, M. Szirmay-Kalos, L. Szymanski, B. Tadeusiewicz, R. Tadic, B. Talia, D. Tan, G. Taylor, S.J.E. Teixeira, J.C. Telelis, O.A. Teo, Y.M Teresco, J. Teyssiere, G. Thalmann, D. Theodoropoulos, G. Theoharis, T. Thurner, S. Tirado-Ramos, A. Tisserand, A. Toda, K. Tonellotto, N. Torelli, L. Torenvliet, L. Tran, V.D. Truong, H.L. Tsang, K. Tse, K.L. Tvrdik, P. Tzevelekas, L. Uthayopas, P. Valencia, P. Vassilakis, C. Vaughan, F. Vazquez, P.P. Venticinque, S. Vigo-Aguiar, J. Vivien, F. Volkert, J. Wada, K. Walter, M. Wasniewski, J. Wasserbauer, A.
Organization
Watson, G. Wawrzyniak, D. Weglarz, J. Weidendorfer, J. Weispfenning, W. Wendelborn, A.L. Weron, R. Wismüller, R. Wojciechowski, K. Wolf, F. Worring, M. Wyrzykowski, R.
Xiao, Y. Xu, J. Xue, Y. Yahyapour, R. Yan, N. Yang, K. Yener, B. Yoo, S.M. Yu, J.H. Yu, Z.C.H. Zara, J. Zatevakhin, M.A.
XIII
Zhang, J.W. Zhang, N.X.L. Zhang, X. Zhao, L. Zhmakin, A.I. Zhu, W.Z. Zlatev, Z. Zomaya, A. Zudilova, E.V.
Workshops Organizers Programming Grids and Metasystems V. Sunderam (Emory University, USA) D. Kurzyniec (Emory University, USA) V. Getov (University of Westminster, UK) M. Malawski (Institute of Computer Science and CYFRONET AGH, Poland) Active and Programmable Grids Architectures and Components C. Anglano (Università del Piemonte Orientale, Italy) F. Baumgartner (University of Bern, Switzerland) G. Carle (Tubingen University, Germany) X. Cheng (Institute of Computing Technology, Chinese Academy of Science, ROC) K. Chen (Institut Galilée, Université Paris 13, France) S. Denazis (Hitachi Europe, France) B. Dhoedt (University of Gent, Belgium) W. Donnelly (Waterford Institute of Technology, Ireland) A. Galis (University College London, UK) A. Gavras (Eurescom, Germany) F. Gagliardi (CERN, Switzerland) Y. Gourhant (France Telecom, France) M. Gilbert (European Microsoft Innovation Center, Microsoft Corporation, Germany) A. Juhola (VTT, Finland) C. Klein (Siemens, Germany) D. Larrabeiti (University Carlos III, Spain) L. Lefevre (INRIA, France) F. Leymann (IBM, Germany) H. de Meer (University of Passau, Germany) G. H. Petit (Alcatel, Belgium)
XIV
Organization
J. Serrat (Universitat Politècnica de Catalunya, Spain) E. Scharf (QMUL, UK) K. Skala (Ruder Boskoviç Institute, Croatia) N. Shrikhande (European Microsoft Innovation Center, Microsoft Corporation, Germany) M. Solarski (FhG FOKUS, Germany) D. Raz (Technion Institute of Technology, Israel) (AGH University of Science and Technology, Poland) R. Yahyapour (University Dortmund, Germany) K. Yang (University of Essex, UK) Next Generation Computing E.-N. John Huh (Seoul Women’s University, Korea) Practical Aspects of High-Level Parallel Programming (PAPP 2004) F. Loulergue (Laboratory of Algorithms, Complexity and Logic, University of Paris Val de Marne, France) Parallel Input/Output Management Techniques (PIOMT 2004) J. H. Abawajy (Carleton University, School of Computer Science, Canada) OpenMP for Large Scale Applications B. Chapman (University of Houston, USA) Tools for Program Development and Analysis in Computational Science D. Kranzlmüller (Johannes Kepler University Linz, Austria) R. Wismüller (TU München, Germany) A. Bode (Technische Universität München, Germany) J. Volkert (Johannes Kepler University Linz, Austria) Modern Technologies for Web-Based Adaptive Systems N. Thanh Nguyen University of Technology, Poland) J. Sobecki University of Technology, Poland) Agent Day 2004 – Intelligent Agents in Computing Systems E. Nawarecki (AGH University of Science and Technology, Poland) K. Cetnarowicz (AGH University of Science and Technology, Poland) G. Dobrowolski (AGH University of Science and Technology, Poland) R. Schaefer (Jagiellonian University, Poland) S. Ambroszkiewicz (Polish Academy of Sciences, Warsaw, Poland) A. Koukam (Université de Belfort-Montbeliard, France) V. Srovnal (VSB Technical University of Ostrava, Czech Republic) C. Cotta (Universidad de Málaga, Spain) S. Raczynski (Universidad Panamericana, Mexico)
Organization
XV
Dynamic Data Driven Application Systems F. Darema (NSF/CISE, USA) HLA-Based Distributed Simulation on the Grid S. J. Turner (Nanyang Technological University, Singapore) Interactive Visualisation and Interaction Technologies E. Zudilova (University of Amsterdam, The Netherlands) T. Adriaansen (CSIRO, ICT Centre, Australia) Computational Modeling of Transport on Networks B. Tadic (Jozef Stefan Institute, Slovenia) S. Thurner (Universität Wien, Austria) Modeling and Simulation in Supercomputing and Telecommunications Y. Mun (Soongsil University, Korea) QoS Routing H. Choo (Sungkyunkwan University, Korea) Evolvable Hardware N. Nedjah (State University of Rio de Janeiro, Brazil) L. de Macedo Mourelle (State University of Rio de Janeiro, Brazil) Advanced Methods of Digital Image Processing B. Smolka (Silesian University of Technology, Laboratory of Multimedia Communication, Poland) Computer Graphics and Geometric Modelling (CGGM 2004) A. Iglesias Prieto (University of Cantabria, Spain) Computer Algebra Systems and Applications (CASA 2004) A. Iglesias Prieto (University of Cantabria, Spain) A. Galvez (University of Cantabria, Spain) New Numerical Methods for DEs: Applications to Linear Algebra, Control and Engineering N. Del Buono (University of Bari, Italy) L. Lopez (University of Bari, Italy) Parallel Monte Carlo Algorithms for Diverse Applications in a Distributed Setting V. N. Alexandrov (University of Reading, UK) A. Karaivanova (Bulgarian Academy of Sciences, Bulgaria) I. Dimov (Bulgarian Academy of Sciences, Bulgaria)
XVI
Organization
Modelling and Simulation of Multi-physics Multi-scale Systems V. Krzhizhanovskaya (University of Amsterdam, The Netherlands) B. Chopard (University of Geneva, CUI, Switzerland) Y. Gorbachev (St. Petersburg State Polytechnical University, Russia) Gene, Genome and Population Evolution S. Cebrat (University of Poland) D. Stauffer (Cologne University, Germany) A. Maksymowicz (AGH University of Science and Technology, Poland) Computational Methods in Finance and Insurance A. Janicki (University of Poland) J.J. Korczak (University Louis Pasteur, Strasbourg, France) Computational Economics and Finance X. Deng (City University of Hong Kong, Hong Kong) S. Wang (Chinese Academy of Sciences, ROC) Y. Shi (University of Nebraska at Omaha, USA) GeoComputation Y. Xue (Chinese Academy of Sciences, ROC) C. Yarotsos (University of Athens, Greece) Simulation and Modeling of 3D Integrated Circuits I. Balk (R3Logic Inc., USA) Computational Modeling and Simulation on Biomechanical Engineering Y.H. Kim (Kyung Hee University, Korea) Information Technologies Enhancing Health Care Delivery M. Duplaga (Jagiellonian University Medical College, Poland) D. Ingram (University College London, UK) (AGH University of Science and Technology, Poland) Computing in Science and Engineering Academic Programs D. Donnelly (Siena College, USA)
Organization
Sponsoring Institutions Hewlett-Packard Intel SGI ATM SUN Microsystems IBM Polish Airlines LOT ACC CYFRONET AGH Institute of Computer Science AGH Polish Ministry of Scientific Research and Information Technology Springer-Verlag
XVII
This page intentionally left blank
Table of Contents – Part III
Workshop on Programming Grids and Metasystems High-Performance Parallel and Distributed Scientific Computing with the Common Component Architecture D.E. Bernholdt Multiparadigm Model Oriented to Development of Grid Systems J.L.V. Barbosa, C.A. da Costa, A.C. Yamin, C.F.R. Geyer The Effect of the Generation Clusters: Changes in the Parallel Programming Paradigms J. Porras, P. Huttunen, J. Ikonen
1 2
10
JavaSymphony, a Programming Model for the Grid A. Jugravu, T. Fahringer
18
Adaptation of Legacy Software to Grid Services M. Bubak,
26
Grid Service Registry for Workflow Composition Framework M. Bubak, M. Malawski, K. Rycerz
34
A-GWL: Abstract Grid Workflow Language T. Fahringer, S. Pllana, A. Villazon
42
Design of Departmental Metacomputing ML F. Gava
50
A Grid-Enabled Scene Rendering Application M. Caballer, V. Hernández, J.E. Román
54
Rule-Based Visualization in a Computational Steering Collaboratory L. Jiang, H. Liu, M. Parashar, D. Silver
58
Placement of File Replicas in Data Grid Environments J.H. Abawajy
66
Generating Reliable Conformance Test Suites for Parallel and Distributed Languages, Libraries, and APIs A Concept of Replicated Remote Method Invocation J. Brzezinski, C. Sobaniec
74 82
XX
Table of Contents – Part III
Workshop on First International Workshop on Active and Programmable Grids Architectures and Components Discovery of Web Services with a P2P Network F. Forster, H. De Meer
90
Achieving Load Balancing in Structured Peer-to-Peer Grids C. Pairot, P. García, A.F.G. Skarmeta, R. Mondéjar
98
A Conceptual Model for Grid-Adaptivity of HPC Applications and Its Logical Implementation Using Components Technology A. Machì, S. Lombardo
106
Global Discovery Service for JMX Architecture J. Midura, K. Balos, K. Zielinski
114
Towards a Grid Applicable Parallel Architecture Machine K. Skala, Z. Sojat
119
A XKMS-Based Security Framework for Mobile Grid into the XML Web Services N. Park, K. Moon, J. Jang, S. Sohn
124
A Proposal of Policy-Based System Architecture for Grid Services Management E. Magaña, E. Salamanca, J. Serrat
133
Self-Management GRID Services – A Programmable Network Approach L. Cheng, A. Galis,
141
J. Bešter
Application-Specific Hints in Reconfigurable Grid Scheduling Algorithms B. Volckaert, P. Thysebaert, F. De Turck, B. Dhoedt, P. Demeester
149
Self-Configuration of Grid Nodes Using a Policy-Based Management Architecture F.J. García, Ó. Cánovas, G. Martínez, A.F.G. Skarmeta
158
Context-Aware GRID Services: Issues and Approaches K. Jean, A. Galis, A. Tan
166
Security Issues in Virtual Grid Environments J.L. Muñoz, J. Pegueroles, J. Forné, O. Esparza, M. Soriano
174
Implementation and Evaluation of Integrity Protection Facilities for Active Grids J. Bešter
179
Table of Contents – Part III
A Convergence Architecture for GRID Computing and Programmable Networks C. Bachmeir, P. Tabery, D. Marinov, G. Nachev, J. Eberspächer Programmable Grids Framework Enabling QoS in an OGSA Context J. Soldatos, L. Polymenakos, G. Kormentzas Active and Logistical Networking for Grid Computing: The E-toile Architecture A. Bassi, M. Beck, F. Chanussot, J.-P. Gelas, R. Harakaly, L. Lefèvre, T. Moore, J. Plank, P. Primet
XXI
187 195
202
Distributed Resource Discovery in Wide Area Grid Environments T.N. Ellahi, M.T. Kechadi
210
Trusted Group Membership Service for JXTA L. Kawulok, K. Zielinski, M. Jaeschke
218
Workshop on Next Generation Computing An Implementation of Budget-Based Resource Reservation for Real-Time Linux C. S. Liu, N.C. Perng, T.W. Kuo
226
Similarity Retrieval Based on SOM-Based R*-Tree K.H. Choi, M.H. Shin, S.H. Bae, C.H. Kwon, I.H. Ra
234
Extending the Power of Server Based Computing H.L. Yu, W.M. Zhen, M.M. Shen
242
Specifying Policies for Service Negotiations of Response Time T.K. Kim, O.H. Byeon, K.J. Chun, T.M. Chung
250
Determination and Combination of Quantitative Weight Value from Multiple Preference Information J.H. Yoo, B.G. Lee, H.S. Han
258
Forwarding Based Data Parallel Handoff for Real-Time QoS in Mobile IPv6 Networks H. Y. Jeong, J. Lim, J.D. Park, H. Choo
266
Mobile Agent-Based Load Monitoring System for the Safety Web Server Environment H.J. Park, K.J. Jyung, S.S. Kim
274
A Study on TCP Buffer Management Algorithm for Improvement of Network Performance in Grid Environment Y. Jeong, M. Noh, H.K. Lee, Y. Mun
281
XXII
Table of Contents – Part III
Workshop on Practical Aspects of High-Level Parallel Programming (PAPP 2004) Evaluating the Performance of Skeleton-Based High Level Parallel Programs A. Benoit, M. Cole, S. Gilmore, J. Hillston
289
Towards a Generalised Runtime Environment for Parallel Haskells J. Berthold
297
Extending Camelot with Mutable State and Concurrency S. Gilmore
306
EVE, an Object Oriented SIMD Library J. Falcou, J. Sérot
314
Petri Nets as Executable Specifications of High-Level Timed Parallel Systems F. Pommereau Parallel I/O in Bulk-Synchronous Parallel ML F. Gava
322 331
Workshop on Parallel Input/Output Management Techniques (PIOMT04) File Replacement Algorithm for Storage Resource Managers in Data Grids J.H. Abawajy
339
Optimizations Based on Hints in a Parallel File System M.S. Pérez, A. Sánchez, V. Robles, J.M. Peña, F. Pérez
347
Using DMA Aligned Buffer to Improve Software RAID Performance Z. Shi, J. Zhang, X. Zhou
355
mNFS: Multicast-Based NFS Cluster W.-G. Lee, C.-I. Park, D.-W. Kim
363
Balanced RM2: An Improved Data Placement Scheme for Tolerating Double Disk Failures in Disk Arrays D.-W. Kim, S.-H. Lee, C.-I. Park
371
Diagonal Replication on Grid for Efficient Access of Data in Distributed Database Systems M. Mat Deris, N. Bakar, M. Rabiei, H.M. Suzuri
379
Table of Contents – Part III
XXIII
Workshop on OpenMP for Large Scale Applications Performance Comparison between OpenMP and MPI on IA64 Architecture L. Qi, M. Shen, Y. Chen, J. Li
388
Defining Synthesizable OpenMP Directives and Clauses P. Dziurzanski, V. Beletskyy
398
Efficient Translation of OpenMP to Distributed Memory L. Huang, B. Chapman, Z. Liu, R. Kendall
408
ORC-OpenMP: An OpenMP Compiler Based on ORC Y. Chen, J. Li, S. Wang, D. Wang
414
Workshop on Tools for Program Development and Analysis in Computational Science Performance Analysis, Data Sharing, and Tools Integration in Grids: New Approach Based on Ontology H.-L. Truong, T. Fahringer Accurate Cache and TLB Characterization Using Hardware Counters J. Dongarra, S. Moore, P. Mucci, K. Seymour, H. You
424 432
A Tool Suite for Simulation Based Analysis of Memory Access Behavior J. Weidendorfer, M. Kowarschik, C. Trinitis
440
Platform-Independent Cache Optimization by Pinpointing Low-Locality Reuse K. Beyls, E.H. D’Hollander
448
Teuta: Tool Support for Performance Modeling of Distributed and Parallel Applications T. Fahringer, S. Pllana, J. Testori
456
MPI Application Development Using the Analysis Tool MARMOT B. Krammer, M.S. Müller, M.M. Resch
464
Monitoring System for Distributed Java Applications W. Funika, M. Bubak,
472
Automatic Parallel-Discrete Event Simulation M. Marín
480
XXIV
Table of Contents – Part III
Workshop on Modern Technologies for Web-Based Adaptive Systems Creation of Information Profiles in Distributed Databases as a Game J.L. Kulikowski
488
Domain Knowledge Modelling for Intelligent Instructional Systems E. Pecheanu, L. Dumitriu, C. Segal
497
Hybrid Adaptation of Web-Based Systems User Interfaces J. Sobecki
505
Collaborative Web Browsing Based on Ontology Learning from Bookmarks J.J. Jung, Y.-H. Yu, G.-S. Jo
513
Information Retrieval Using Bayesian Networks L. Neuman, J. Kozlowski, A. Zgrzywa
521
An Application of the DEDS Control Synthesis Method
529
Using Consistency Measures and Attribute Dependencies for Solving Conflicts in Adaptive Systems M. Malowiecki, N. T. Nguyen, M. Zgrzywa
537
Logical Methods for Representing Meaning of Natural Language Texts T. Batura, F. Murzin
545
Software Self-Adaptability by Means of Artificial Evolution M. Nowostawski, M. Purvis, A. Gecow
552
Professor:e – An IMS Standard Based Adaptive E-learning Platform C. Segal, L. Dumitriu
560
Workshop on Agent Day 2004 – Intelligent Agents in Computing Systems Towards Measure of Semantic Correlation between Messages in Multiagent System R. Katarzyniak Modelling Intelligent Virtual Agent Skills with Human-Like Senses P. Herrero, A. de Antonio
567 575
Table of Contents – Part III
XXV
Reuse of Organisational Experience Harnessing Software Agents K. Krawczyk, M. Majewska, M. Dziewierz, Z. Balogh, J. Kitowski, S. Lambert
583
The Construction and Analysis of Agent Fault-Tolerance Model Based on Y. Jiang, Z. Xia, Y. Zhong, S. Zhang
591
REMARK – Reusable Agent-Based Experience Management and Recommender Framework Z. Balogh, M. Laclavik, L. Hluchy, I. Budinska, K. Krawczyk
599
Behavior Based Detection of Unfavorable Resources K. Cetnarowicz, G. Rojek
607
Policy Modeling in Four Agent Economy
615
Multi-agent System for Irregular Parallel Genetic Computations J. Momot, K. Kosacki, M. Grochowski, P. Uhruski, R. Schaefer
623
Strategy Extraction for Mobile Embedded Control Systems Apply the Multi-agent Technology V. Srovnal, B. Horák, R. Bernatík, V. Snášel
631
Multi-agent Environment for Dynamic Transport Planning and Scheduling J. Kozlak, J.-C. Créput, V. Hilaire, A. Koukam
638
Agent-Based Models and Platforms for Parallel Evolutionary Algorithms M. Kisiel-Dorohinicki
646
A Co-evolutionary Multi-agent System for Multi-modal Function Optimization
654
Workshop on Dynamic Data Driven Applications Systems Dynamic Data Driven Applications Systems: A New Paradigm for Application Simulations and Measurements F. Darema Distributed Collaborative Adaptive Sensing for Hazardous Weather Detection, Tracking, and Predicting J. Brotzge, V. Chandresakar, K. Droegemeier, J. Kurose, D. McLaughlin, B. Philips, M. Preston, S. Sekelsky
662
670
XXVI
Table of Contents – Part III
Rule-Based Support Vector Machine Classifiers Applied to Tornado Prediction T.B. Trafalis, B. Santosa, M.B. Richman Adaptive Coupled Physical and Biogeochemical Ocean Predictions: A Conceptual Basis P.F.J. Lermusiaux, C. Evangelinos, R. Tian, P.J. Haley, J.J. McCarthy, N.M. Patrikalakis, A.R. Robinson, H. Schmidt Dynamic-Data-Driven Real-Time Computational Mechanics Environment J. Michopoulos, C. Farhat, E. Houstis
678
685
693
A Note on Data-Driven Contaminant Simulation C.C. Douglas, C.E. Shannon, Y. Efendiev, R. Ewing, V. Ginting, R. Lazarov, M.J. Cole, G. Jones, C.R. Johnson, J. Simpson
701
Computational Aspects of Data Assimilation for Aerosol Dynamics A. Sandu, W. Liao, G.R. Carmichael, D. Henze, J.H. Seinfeld, T. Chai, D. Daescu
709
A Framework for Online Inversion-Based 3D Site Characterization V. Akçelik, J. Bielak, G. Biros, I. Epanomeritakis, O. Ghattas, L.F. Kallivokas, E.J. Kim
717
A Note on Dynamic Data Driven Wildfire Modeling J. Mandel, M. Chen, L.P. Franca, C. Johns, A. Puhalskii, J.L. Coen, C.C. Douglas, R. Kremens, A. Vodacek, W. Zhao
725
Agent-Based Simulation of Data-Driven Fire Propagation Dynamics J. Michopoulos, P. Tsompanopoulou, E. Houstis, A. Joshi
732
Model Reduction of Large-Scale Dynamical Systems A. Antoulas, D. Sorensen, K.A. Gallivan, P. Van Dooren, A. Grama, C. Hoffmann, A. Sameh
740
Data Driven Design Optimization Methodology Development and Application H. Zhao, D. Knight, E. Taskinoglu, V. Jovanovic A Dynamic Data Driven Computational Infrastructure for Reliable Computer Simulations J.T. Oden, J.C. Browne, I. Babuška, C. Bajaj, L.F. Demkowicz, L. Gray, J. Bass, Y. Feng, S. Prudhomme, F. Nobile, R. Tempone Improvements to Response-Surface Based Vehicle Design Using a Feature-Centric Approach D. Thompson, S. Parthasarathy, R. Machiraju, S. Lawrence
748
756
764
Table of Contents – Part III
An Experiment for the Virtual Traffic Laboratory: Calibrating Speed Dependency on Heavy Traffic (A Demonstration of a Study in a Data Driven Trafic Analysis) A. Visser, J. Zoetebier, H. Yakali, B. Hertzberger SAMAS: Scalable Architecture for Multi-resolution Agent-Based Simulation A. Chaturvedi, J. Chi, S. Mehta, D. Dolk
XXVII
771
779
Simulation Coercion Applied to Multiagent DDDAS Y. Loitière, D. Brogan, P. Reynolds
789
O’SOAP – A Web Services Framework for DDDAS Applications K. Pingali, P. Stodghill
797
Application of Grid-Enabled Technologies for Solving Optimization Problems in Data-Driven Reservoir Studies M. Parashar, H. Klie, U. Catalyurek, T. Kurc, V. Matossian, J. Saltz, M.F. Wheeler Image-Based Stress Recognition Using a Model-Based Dynamic Face Tracking System D. Metaxas, S. Venkataraman, C. Vogler Developing a Data Driven System for Computational Neuroscience R. Snider, Y. Zhu Karhunen–Loeve Representation of Periodic Second-Order Autoregressive Processes D. Lucor, C.-H. Su, G.E. Karniadakis
805
813 822
827
Workshop on HLA-Based Distributed Simulation on the Grid Using Web Services to Integrate Heterogeneous Simulations in a Grid Environment J.M. Pullen, R. Brunton, D. Brutzman, D. Drake, M. Hieb, K.L. Morse, A. Tolk Support for Effective and Fault Tolerant Execution of HLA-Based Applications in the OGSA Framework K. Rycerz, M. Bubak, M. Malawski, P.M.A. Sloot
835
848
Federate Migration in HLA-Based Simulation Z. Yuan, W. Cai, M.Y.H. Low, S.J. Turner
856
FT-RSS: A Flexible Framework for Fault Tolerant HLA Federations J. Lüthi, S. Großmann
865
XXVIII
Table of Contents – Part III
Design and Implementation of GPDS T.-D. Lee, S.-H. Yoo, C.-S. Jeong HLA_AGENT: Distributed Simulation of Agent-Based Systems with HLA M. Lees, B. Logan, T. Oguara, G. Theodoropoulos FedGrid: An HLA Approach to Federating Grids S. Vuong, X. Cai, J. Li, S. Pramanik, D. Suttles, R. Chen
873
881 889
Workshop on Interactive Visualisation and Interaction Technologies Do Colors Affect Our Recognition Memory for Haptic Rough Surfaces? Z. Luo, A. Imamiya
897
Enhancing Human Computer Interaction in Networked Hapto-Acoustic Virtual Reality Environments on the CeNTIE Network T. Adriaansen, A. Krumm-Heller, C. Gunn
905
Collaborative Integration of Speech and 3D Gesture for Map-Based Applications A. Corradini
913
Mobile Augmented Reality Support for Architects Based on Feature Tracking Techniques M. Bang Nielsen, G. Kramp, K. Grønbæk
921
User Interface Design for a Navigation and Communication System in the Automotive World O. Preißner
929
Target Selection in Augmented Reality Worlds J. Sands, S. W. Lawson, D. Benyon Towards Believable Behavior Generation for Embodied Conversational Agents A. Corradini, M. Fredriksson, M. Mehta, J. Königsmann, N.O. Bernsen, L. Johannesson A Performance Analysis of Movement Patterns C. Sas, G. O’Hare, R. Reilly On the Motivation and Attractiveness Scope of the Virtual Reality User Interface of an Educational Game M. Virvou, G. Katsionis, K. Manos
936
946
954
962
Table of Contents – Part III
A Client-Server Engine for Parallel Computation of High-Resolution Planes D.P. Gavidia, E. V. Zudilova, P.M.A. Sloot
XXIX
970
A Framework for 3D Polysensometric Comparative Visualization J.I. Khan, X. Xu, Y. Ma
978
An Incremental Editor for Dynamic Hierarchical Drawing of Trees D. Workman, M. Bernard, S. Pothoven
986
Using Indexed-Sequential Geometric Glyphs to Explore Visual Patterns J. Morey, K. Sedig
996
Studying the Acceptance or Rejection of Newcomers in Virtual Environments P. Herrero, A. de Antonio, J. Segovia
1004
Open Standard Based Visualization of Complex Internet Computing Systems S.S. Yang, J.I. Khan
1008
General Conception of the Virtual Laboratory M. Lawenda, N. Meyer, T. Rajtar, Z. Gdaniec, R. W. Adamiak
1013
Individual Differences in Virtual Environments C. Sas
1017
Ecological Strategies and Knowledge Mapping J. Bidarra, A. Dias
1025
Need for a Prescriptive Taxonomy of Interaction for Mathematical Cognitive Tools K. Sedig
1030
Workshop on Computational Modeling of Transport on Networks Evolution of the Internet Map and Load Distribution K.-I. Goh, B. Kahng, D. Kim
1038
Complex Network of Earthquakes S. Abe, N. Suzuki
1046
Universal Features of Network Topology K. Austin, G.J. Rodgers
1054
XXX
Table of Contents – Part III
Network Brownian Motion: A New Method to Measure Vertex-Vertex Proximity and to Identify Communities and Subcommunities H. Zhou, R. Lipowsky
1062
Contagion Flow through Banking Networks M. Boss, M. Summer, S. Thurner
1070
Local Search with Congestion in Complex Communication Networks A. Arenas, L. Danon, A. Díaz-Guilera, R. Guimerà
1078
Guided Search and Distribution of Information Flow on Complex Graphs Network Topology in Immune System Shape Space J. Burns, H.J. Ruskin
1086 1094
An Evolutionary Approach to Pickup and Delivery Problem with Time Windows J.-C. Créput, A. Koukam, J. Kozlak, J. Lukasik
1102
Automatic Extraction of Hierarchical Urban Networks: A Micro-Spatial Approach R. Carvalho, M. Batty
1109
Workshop on Modeling and Simulation in Supercomputing and Telecommunications Design and Implementation of the Web-Based PSE GridGate K. Kang, Y. Kang, K. Cho
1117
Performance Evaluation of ENUM Directory Service Design H.K. Lee, Y. Mun
1124
A Single Thread Discrete Event Simulation Toolkit for Java: STSimJ W. Chen, D. Wang, W. Zheng
1131
Routing and Wavelength Assignments in Optical WDM Networks with Maximum Quantity of Edge Disjoint Paths H. Choo, V.V. Shakhov
1138
Parallelism for Nested Loops with Non-uniform and Flow Dependences S.-J. Jeong
1146
Comparison Based Diagnostics as a Probabilistic Deduction Problem B. Polgár
1153
Table of Contents – Part III
XXXI
Dynamic Threshold for Monitor Systems on Grid Service Environments E.N. Huh
1162
Multiuser CDMA Parameters Estimation by Particle Filter with Resampling Schemes J.-S. Kim, D.-R. Shin, W.-G. Chung
1170
Workshop on QoS Routing Routing, Wavelength Assignment in Optical Networks Using an Efficient and Fair EDP Algorithm P. Manohar, V. Sridhar
1178
Route Optimization Technique to Support Multicast in Mobile Networks K. Park, S. Han, B.-g. Joo, K. Kim, J. Hong
1185
PRED: Prediction-Enabled RED M.G. Chung, E.N. Huh An Efficient Aggregation and Routing Algorithm Using Multi-hop Clustering in Sensor Networks B.-H. Lee, H.-W. Yoon, T.-J. Lee, M.Y. Chung Explicit Routing for Traffic Engineering in Labeled Optical Burst-Switched WDM Networks J. Zhang, H.-J. Lee, S. Wang, X. Qiu, K. Zhu, Y. Huang, D. Datta, Y.-C. Kim, B. Mukherjee A Mutual Authentication and Route Optimization Method between MN and CN Using AAA in Mobile IPv6 M. Kim, H.K. Lee, Y. Mun Studies on a Class of AWG-Based Node Architectures for Optical Burst-Switched Networks Y. Huang, D. Datta, X. Qiu, J. Zhang, H.-K. Park, Y.-C. Kim, J.P. Heritage, B. Mukherjee Self-Organizing Sensor Networks D. Bein, A.K. Datta
1193
1201
1209
1217
1224
1233
XXXII
Table of Contents – Part III
Workshop on Evolvable Hardware The Application of GLS Algorithm to 2 Dimension Irregular-Shape Cutting Problem P. Kominek
1241
Biologically-Inspired: A Rule-Based Self-Reconfiguration of a Virtex Chip G. Tufte, P.C. Haddow
1249
Designing Digital Circuits for the Knapsack Problem M. Oltean, M. Oltean Improvements in FSM Evolutions from Partial Input/Output Sequences S.G. Araújo, A. Mesquita, A.C.P. Pedroza Intrinsic Evolution of Analog Circuits on a Programmable Analog Multiplexer Array J.F.M. Amaral, J.L.M. Amaral, C.C. Santini, M.A.C. Pacheco, R. Tanscheit, M.H. Szwarcman Encoding Multiple Solutions in a Linear Genetic Programming Chromosome M. Oltean, M. Oltean
1257
1265
1273
1281
Evolutionary State Assignment for Synchronous Finite State Machines N. Nedjah, L. de Macedo Mourelle
1289
Author Index
1297
Table of Contents – Part I
Track on Parallel and Distributed Computing Optimization of Collective Reduction Operations R. Rabenseifner
1
Predicting MPI Buffer Addresses F. Freitag, M. Farreras, T. Cortes, J. Labarta
10
An Efficient Load-Sharing and Fault-Tolerance Algorithm in Internet-Based Clustering Systems I.-B. Choi, J.-D. Lee
18
Dynamic Parallel Job Scheduling in Multi-cluster Computing Systems J.H. Abawajy
27
Hunting for Bindings in Distributed Object-Oriented Systems
35
Design and Implementation of the Cooperative Cache for PVFS I.-C. Hwang, H. Kim, H. Jung, D.-H. Kim, H. Ghim, S.-R. Maeng, J.-W. Cho
43
Track on Grid Computing Towards OGSA Compatibility in Alternative Metacomputing Frameworks G. Stuer, V. Sunderam, J. Broeckhove DartGrid: Semantic-Based Database Grid Z. Wu, H. Chen, Changhuang, G. Zheng, J. Xu A 3-tier Grid Architecture and Interactive Applications Framework for Community Grids O. Ardaiz, K. Sanjeevan, R. Sanguesa Incorporation of Middleware and Grid Technologies to Enhance Usability in Computational Chemistry Applications J.P. Greenberg, S. Mock, M. Katz, G. Bruno, F. Sacerdoti, P. Papadopoulos, K.K. Baldridge
51 59
67
75
XXXIV
Table of Contents – Part I
An Open Grid Service Environment for Large-Scale Computational Finance Modeling Systems C. Wiesinger, D. Giczi, R. Hochreiter The Migrating Desktop as a GUI Framework for the “Applications on Demand” Concept M. Kupczyk, N. Meyer, B. Palak, P. Wolniewicz Interactive Visualization for the UNICORE Grid Environment K. Benedyczak, J. Wypychowski
83
91
99
Efficiency of the GSI Secured Network Transmission M. Bubak, T. Szepieniec
107
An Idle Compute Cycle Prediction Service for Computational Grids S. Hwang, E.-J. Im, K. Jeong, H. Park
116
Infrastructure for Grid-Based Virtual Organizations L. Hluchy, O. Habala, V.D. Tran, B. Simo, J. Astalos, M. Dobrucky
124
Air Pollution Modeling in the CrossGrid Project J. C. Mouriño, M.J. Martín, P. González, R. Doallo
132
The Genetic Algorithms Population Pluglet for the H2O Metacomputing System D. Kurzyniec, V. Sunderam, H. Witek
140
Applying Grid Computing to the Parameter Sweep of a Group Difference Pseudopotential W. Sudholt, K.K. Baldridge, D. Abramson, C. Enticott, S. Garic
148
A Grid Enabled Parallel Hybrid Genetic Algorithm for SPN G.L. Presti, G.L. Re, P. Storniolo, A. Urso An Atmospheric Sciences Workflow and Its Implementation with Web Services D. Abramson, J. Kommineni, J.L. McGregor, J. Katzfey Twins: 2-hop Structured Overlay with High Scalability J. Hu, H. Dong, W. Zheng, D. Wang, M. Li Dispatching Mechanism of an Agent-Based Distributed Event System O.K. Sahingoz, N. Erdogan An Adaptive Communication Mechanism for Highly Mobile Agents J. Ahn
156
164 174
184 192
Table of Contents – Part I
XXXV
Track on Models and Algorithms Knapsack Model and Algorithm for HW/SW Partitioning Problem A. Ray, W. Jigang, S. Thambipillai
200
A Simulated Annealing Algorithm for the Circles Packing Problem D. Zhang, W. Huang
206
Parallel Genetic Algorithm for Graph Coloring Problem K. Kwarciany
215
Characterization of Efficiently Parallel Solvable Problems on a Class of Decomposable Graphs S.-Y. Hsieh
223
The Computational Complexity of Orientation Search in Cryo-Electron Microscopy T. Mielikäinen, J. Ravantti, E. Ukkonen
231
Track on Data Mining and Data Bases Advanced High Performance Algorithms for Data Processing A.V. Bogdanov, A.V. Boukhanovsky
239
Ontology-Based Partitioning of Data Steam for Web Mining: A Case Study of Web Logs J.J. Jung
247
Single Trial Discrimination between Right and Left Hand Movement-Related EEG Activity S. Cho, J.A. Kim, D.-U. Hwang, S.K. Han
255
WINGS: A Parallel Indexer for Web Contents F. Silvestri, S. Orlando, R. Perego
263
A Database Server for Predicting Protein-Protein Interactions K. Han, B. Park
271
PairAnalyzer: Extracting and Visualizing RNA Structure Elements Formed by Base Pairing D. Lim, K. Han A Parallel Crawling Schema Using Dynamic Partition S. Dong, X. Lu, L. Zhang
279 287
XXXVI
Table of Contents – Part I
Hybrid Collaborative Filtering and Content-Based Filtering for Improved Recommender System K.-Y. Jung, D.-H. Park, J.-H. Lee
295
Object-Oriented Database Mining: Use of Object Oriented Concepts for Improving Data Classification Technique K. Waiyamai, C. Songsiri, T. Rakthanmanon
303
Data-Mining Based Skin-Color Modeling Using the ECL Skin-Color Images Database M. Hammami, D. Tsishkou, L. Chen
310
Maximum Likelihood Based Quantum Set Separation S. Imre, F. Balázs Chunking-Coordinated-Synthetic Approaches to Large-Scale Kernel Machines F.J. González-Castaño, R.R. Meyer Computational Identification of -1 Frameshift Signals S. Moon, Y. Byun, K. Han
318
326 334
Track on Networking Mobility Management Scheme for Reducing Location Traffic Cost in Mobile Networks B.-M. Min, J.-G. Jee, H.S. Oh
342
Performance Analysis of Active Queue Management Schemes for IP Network J. Koo, S. Ahn, J. Chung
349
A Real-Time Total Order Multicast Protocol K. Erciyes,
357
A Rule-Based Intrusion Alert Correlation System for Integrated Security Management S.-H. Lee, H.-H. Lee, B.-N. Noh
365
Stable Neighbor Based Adaptive Replica Allocation in Mobile Ad Hoc Networks Z. Jing, S. Jinshu, Y. Kan, W. Yijie
373
Mobile-Based Synchronization Model for Presentation of Multimedia Objects K.-W. Lee, H.-S. Cho, K.-H. Lee
381
Table of Contents – Part I
Synchronization Scheme of Multimedia Streams in Mobile Handoff Control G.-S. Lee
XXXVII
389
Poster Papers The Development of a Language for Specifying Structure of a Distributed and Parallel Application R. Dew, P. Horan, A. Goscinski Communication Primitives for Minimally Synchronous Parallel ML F. Loulergue Dependence Analysis of Concurrent Programs Based on Reachability Graph and Its Applications X. Qi, B. Xu
397 401
405
Applying Loop Tiling and Unrolling to a Sparse Kernel Code E. Herruzo, G. Bandera, O. Plata
409
A Combined Method for Texture Analysis and Its Application Y. Zhang, R. Wang
413
Reliability of Cluster System with a Lot of Software Instances M. Szymczyk, P. Szymczyk
417
A Structural Complexity Measure for UML Class Diagrams B. Xu, D. Kang, J. Lu
421
Parallelizing Flood Models with MPI: Approaches and Experiences V.D. Tran, L. Hluchy
425
Using Parallelism in Experimenting and Fine Tuning of Parameters for Metaheuristics M. Blesa, F. Xhafa
429
DEVMA: Developing Virtual Environments with Awareness Models P. Herrero, A. de Antonio
433
A Two-Leveled Mobile Agent System for E-commerce with Constraint-Based Filtering O.K. Sahingoz, N. Erdogan
437
ABSDM: Agent Based Service Discovery Mechanism in Internet S. Li, C. Xu, Z. Wu, Y. Pan, X. Li
441
XXXVIII
Table of Contents – Part I
Meta Scheduling Framework for Workflow Service on the Grids S. Hwang, J. Choi, H. Park
445
Resources Virtualization in Fault-Tolerance and Migration Issues G. Jankowski, R. Mikolajczak, R. Januszewski, N. Meyer,
449
On the Availability of Information Dispersal Scheme for Distributed Storage Systems S.K. Song, H.Y. Youn, G.-L. Park, K.S. Tae
453
Virtual Storage System for the Grid Environment D. Nikolow, J. Kitowski,
458
Performance Measurement Model in the G-PM Tool R. Wismüller, M. Bubak, W. Funika, M. Kurdziel
462
Paramedir: A Tool for Programmable Performance Analysis G. Jost, J. Labarta, J. Gimenez
466
Semantic Browser: an Intelligent Client for Dart-Grid Y. Mao, Z. Wu, H. Chen
470
On Identity-Based Cryptography and GRID Computing H.W. Lim, M.J.B. Robshaw
474
The Cambridge CFD Grid Portal for Large-Scale Distributed CFD Applications X. Yang, M. Hayes, K. Jenkins, S. Cant
478
Grid Computing Based Simulations of the Electrical Activity of the Heart J.M. Alonso, V. Hernández, G. Moltó
482
Artificial Neural Networks and the Grid E. Schikuta, T. Weishäupl
486
Towards a Grid-Aware Computer Algebra System D. Petcu, D. Dubu, M. Paprzycki
490
Grid Computing and Component-Based Software Engineering in Computer Supported Collaborative Learning M.L. Bote-Lorenzo, J.I. Asensio-Pérez, G. Vega-Gorgojo, L.M. Vaquero-González, E. Gómez-Sánchez, Y.A. Dimitriadis An NAT-Based Communication Relay Scheme for Private-IP-Enabled MPI over Grid Environments S. Choi, K. Park, S. Han, S. Park, O. Kwon, Y. Kim, H. Park
495
499
Table of Contents – Part I
A Knowledge Fusion Framework in the Grid Environment J. Gou, J. Yang, H. Qi A Research of Grid Manufacturing and Its Application in Custom Artificial Joint L. Chen, H. Deng, Q. Deng, Z. Wu
XXXIX
503
507
Toward a Virtual Grid Service of High Availability X. Zhi, W. Tong
511
The Measurement Architecture of the Virtual Traffic Laboratory A. Visser, J. Zoetebier, H. Yakali, B. Hertzberger
515
Adaptive QoS Framework for Multiview 3D Streaming J.R. Kim, Y. Won, Y. Iwadate
519
CORBA-Based Open Platform for Processes Monitoring. An Application to a Complex Electromechanical Process K. Cantillo, R.E. Haber, J.E. Jiménez, Á. Alique, R. Galán
523
An Approach to Web-Oriented Discrete Event Simulation Modeling
527
Query Execution Algorithm in Web Environment with Limited Availability of Statistics J. Jezierski, T. Morzy
532
Using Adaptive Priority Controls for Service Differentiation in QoS-Enabled Web Servers M.M. Teixeira, M.J. Santana, R.H. Carlucci Santana
537
On the Evaluation of x86 Web Servers Using Simics: Limitations and Trade-Offs F.J. Villa, M.E. Acacio, J.M. García
541
MADEW: Modelling a Constraint Awareness Model to Web-Based Learning Environments P. Herrero, A. de Antonio
545
An EC Services System Using Evolutionary Algorithm W.D. Lin
549
A Fast and Efficient Method for Processing Web Documents
553
Online Internet Monitoring System of Sea Regions M. Piotrowski, H. Krawczyk
557
XL
Table of Contents – Part I
Modeling a 3G Power Control Algorithm in the MAC Layer for Multimedia Support U. Pineda, C. Vargas, J. Acosta-Elías, J.M. Luna, G. Pérez, E. Stevens
561
Network Probabilistic Connectivity: Exact Calculation with Use of Chains O.K. Rodionova, A.S. Rodionov, H. Choo
565
A Study of Anycast Application for Efficiency Improvement of Multicast Trees K.-J. Lee, W.-H. Choi, J.-S. Kim
569
Performance Analysis of IP-Based Multimedia Communication Networks to Support Video Traffic A.F. Yaroslavtsev, T.-J. Lee, M.Y. Chung, H. Choo
573
Limited Deflection Routing with QoS-Support H. Kim, S. Lee, J. Song
577
Advanced Multicasting for DVBMT Solution M. Kim, Y.-C. Bang, H. Choo
582
Server Mobility Using Domain Name System in Mobile IPv6 Networks H. Sung, S. Han
586
Resource Reservation and Allocation Method for Next Generation Mobile Communication Systems J. Lee, S.-P. Cho, C. Kang
590
Improved Location Scheme Using Circle Location Register in Mobile Networks D. C. Lee, H. Kim, I.-S. Hwang
594
An Energy Efficient Broadcasting for Mobile Devices Using a Cache Scheme K.-H. Han, J.-H. Kim, Y.-B. Ko, W.-S. Yoon
598
On Balancing Delay and Cost for Routing Paths M. Kim, Y.-C. Bang, H. Choo Performance of Optical Burst Switching in Time Division Multiplexed Wavelength-Routing Networks T.-W. Um, Y. Kwon, J.K. Choi On Algorithm for All-Pairs Most Reliable Quickest Paths Y.-C. Bang, I. Hong, H. Choo
602
607 611
Table of Contents – Part I
Performance Evaluation of the Fast Consistency Algorithms in Large Decentralized Systems J. Acosta-Elías, L. Navarro-Moldes
XLI
615
Building a Formal Framework for Mobile Ad Hoc Computing L. Yan, J. Ni
619
Efficient Immunization Algorithm for Peer-to-Peer Networks H. Chen, H. Jin, J. Sun, Z. Han
623
A Secure Process-Service Model S. Deng, Z. Wu, Z. Yu, L. Huang
627
Multi-level Protection Building for Virus Protection Infrastructure S.-C. Noh, D.C. Lee, K.J. Kim
631
Parallelization of the IDEA Algorithm V. Beletskyy, D. Burak
635
A New Authorization Model for Workflow Management System Using the RPI-RBAC Model S. Lee, Y. Kim, B. Noh, H. Lee
639
Reducing the State Space of RC4 Stream Cipher
644
A Pair-Wise Key Agreement Scheme in Ad Hoc Networks W. Cha, G. Wang, G. Cho
648
Visual Analysis of the Multidimensional Meteorological Data G. Dzemyda
652
Using Branch-Grafted R-trees for Spatial Data Mining P. Dubey, Z. Chen, Y. Shi
657
Using Runtime Measurements and Historical Traces for Acquiring Knowledge in Parallel Applications L.J. Senger, M.J. Santana, R.H.C. Santana Words as Rules: Feature Selection in Text Categorization E. Montañés, E.F. Combarro, I. Díaz, J. Ranilla, J.R. Quevedo
661 666
Proper Noun Learning from Unannotated Corpora for Information Extraction S. -S. Kang
670
Proposition of Boosting Algorithm for Probabilistic Decision Support System M. Wozniak
675
XLII
Table of Contents – Part I
Efficient Algorithm for Linear Pattern Separation C. Tadonki, J.-P. Vial
679
Improved Face Detection Algorithm in Mobile Environment S.-B. Rhee, Y.-H. Lee
683
Real-Time Face Recognition by the PCA (Principal Component Analysis) with Color Images J.O. Kim, S.J. Seo, C.H. Chung
687
Consistency of Global Checkpoints Based on Characteristics of Communication Events in Multimedia Applications M. Ono, H. Higaki
691
Combining the Radon, Markov, and Stieltjes Transforms for Object Reconstruction A. Cuyt, B. Verdonk
695
Author Index
699
Table of Contents – Part II
Track on Numerical Algorithms Hierarchical Matrix-Matrix Multiplication Based on Multiprocessor Tasks S. Hunold, T. Rauber, G. Rünger
1
Improving Geographical Locality of Data for Shared Memory Implementations of PDE Solvers H. Löf, M. Nordén, S. Holmgren
9
Cache Oblivious Matrix Transposition: Simulation and Experiment D. Tsifakis, A.P. Rendell, P.E. Strazdins An Intelligent Hybrid Algorithm for Solving Non-linear Polynomial Systems J. Xue, Y. Li, Y. Feng, L. Yang, Z. Liu A Jacobi–Davidson Method for Nonlinear Eigenproblems H. Voss
17
26 34
Numerical Continuation of Branch Points of Limit Cycles in MATCONT A. Dhooge, W. Govaerts, Y.A. Kuznetsov
42
Online Algorithm for Time Series Prediction Based on Support Vector Machine Philosophy J.M. Górriz, C.G. Puntonet, M. Salmerón
50
Improved A-P Iterative Algorithm in Spline Subspaces J. Xian, S.P. Luo, W. Lin Solving Differential Equations in Developmental Models of Multicellular Structures Expressed Using L-systems P. Federl, P. Prusinkiewicz
58
65
On a Family of A-stable Collocation Methods with High Derivatives G. Y. Kulikov, A.I. Merkulov, E.Y. Khrustaleva
73
Local Sampling Problems S.-Y. Yang, W. Lin
81
XLIV
Table of Contents – Part II
Recent Advances in Semi-Lagrangian Modelling of Flow through the Strait of Gibraltar M. Seaïd, M. El-Amrani, A. Machmoum Efficiency Study of the “Black-Box” Component Decomposition Preconditioning for Discrete Stress Analysis Problems Direct Solver Based on FFT and SEL for Diffraction Problems with Distribution H. Koshigoe
89
97
105
Non-negative Matrix Factorization for Filtering Chinese Document J. Lu, B. Xu, J. Jiang, D. Kang
113
On Highly Secure and Available Data Storage Systems S.J. Choi, H.Y. Youn, H.S. Lee
121
Track on Finite Element Method A Numerical Adaptive Algorithm for the Obstacle Problem F.A. Pérez, J.M. Cascón, L. Ferragut
130
Finite Element Model of Fracture Formation on Growing Surfaces P. Federl, P. Prusinkiewicz
138
An Adaptive, 3-Dimensional, Hexahedral Finite Element Implementation for Distributed Memory J. Hippold, A. Meyer, G. Rünger A Modular Design for Parallel Adaptive Finite Element Computational Kernels Load Balancing Issues for a Multiple Front Method C. Denis, J.P. Boufflet, P. Breitkopf, M. Vayssade, Multiresolutional Techniques in Finite Element Method Solution of Eigenvalue Problem
146
155 163
171
Track on Neural Networks Self-Organizing Multi-layer Fuzzy Polynomial Neural Networks Based on Genetic Optimization S.-K. Oh, W. Pedrycz, H.-K. Kim, J.-B. Lee
179
Table of Contents – Part II
XLV
Information Granulation-Based Multi-layer Hybrid Fuzzy Neural Networks: Analysis and Design B.-J. Park, S.-K. Oh, W. Pedrycz, T.-C. Ahn
188
Efficient Learning of Contextual Mappings by Context-Dependent Neural Nets P. Ciskowski
196
An Unsupervised Neural Model to Analyse Thermal Properties of Construction Materials E. Corchado, P. Burgos, M. Rodríguez, V. Tricio
204
Intrusion Detection Based on Feature Transform Using Neural Network W. Kim, S.-C. Oh, K. Yoon
212
Track on Applications Accelerating Wildland Fire Prediction on Cluster Systems B. Abdalhaq, A. Cortés, T. Margalef, E. Luque
220
High Precision Simulation of Near Earth Satellite Orbits for SAR-Applications M. Kalkuhl, K. Nöh, O. Loffeld, W. Wiechert
228
Hybrid Approach to Reliability and Functional Analysis of Discrete Transport System T. Walkowiak, J. Mazurkiewicz
236
Mathematical Model of Gas Transport in Anisotropic Porous Electrode of the PEM Fuel Cell E. Kurgan, P. Schmidt
244
Numerical Simulation of Anisotropic Shielding of Weak Magnetic Fields E. Kurgan
252
Functionalization of Single-Wall Carbon Nanotubes: An Assessment of Computational Methods B. Akdim, T. Kar, X. Duan, R. Pachter
260
Improved Sampling for Biological Molecules Using Shadow Hybrid Monte Carlo S.S. Hampton, J.A. Izaguirre
268
A New Monte Carlo Approach for Conservation Laws and Relaxation Systems L. Pareschi, M. Seaïd
276
XLVI
Table of Contents – Part II
A Parallel Implementation of Gillespie’s Direct Method A.M. Ridwan, A. Krishnan, P. Dhar Simulation of Deformable Objects Using Sliding Mode Control with Application to Cloth Animation F. Rum, B. W. Gordon
284
292
Constraint-Based Contact Analysis between Deformable Objects M. Hong, M.-H. Choi, C. Lee
300
Prediction of Binding Sites in Protein-Nucleic Acid Complexes N. Han, K. Han
309
Prediction of Protein Functions Using Protein Interaction Data H. Jung, K. Han
317
Interactions of Magainin-2 Amide with Membrane Lipids K. Murzyn, T. Róg, M. Pasenkiewicz-Gierula
325
Dynamics of Granular Heaplets: A Phenomenological Model Y.K. Goh, R.L. Jacobs
332
Modelling of Shear Zones in Granular Materials within Hypoplasticity J. Tejchman
340
Effective Algorithm for Detection of a Collision between Spherical Particles J.S. Leszczynski, M. Ciesielski
348
Vorticity Particle Method for Simulation of 3D Flow H. Kudela, P. Regucki
356
Crack Analysis in Single Plate Stressing of Particle Compounds M. Khanal, W. Schubert, J. Tomas
364
A Uniform and Reduced Mathematical Model for Sucker Rod Pumping L. Liu, C. Tong, J. Wang, R. Liu
372
Distributed Computation of Optical Flow A.G. Dopico, M.V. Correia, J.A. Santos, L.M. Nunes
380
Analytical Test on Effectiveness of MCDF Operations J. Kong, B. Zhang, W. Guo
388
An Efficient Perspective Projection Using VolumePro™ S. Lim, B.-S. Shin
396
Table of Contents – Part II
Reconstruction of 3D Curvilinear Wireframe Model from 2D Orthographic Views A. Zhang, Y. Xue, X. Sun, Y. Hu, Y. Luo, Y. Wang, S. Zhong, J. Wang, J. Tang, G. Cai Surface Curvature Estimation for Edge Spinning Algorithm M. Cermak, V. Skala
XLVII
404
412
Visualization of Very Large Oceanography Time-Varying Volume Datasets S. Park, C. Bajaj, I. Ihm
419
Sphere-Spin-Image: A Viewpoint-Invariant Surface Representation for 3D Face Recognition Y. Wang, G. Pan, Z. Wu, S. Han
427
Design and Implementation of Integrated Assembly Object Model for Intelligent Virtual Assembly Planning J. Fan, Y. Ye, J.-M. Cai
435
Adaptive Model Based Parameter Estimation, Based on Sparse Data and Frequency Derivatives D. Deschrijver, T. Dhaene, J. Broeckhove
443
Towards Efficient Parallel Image Processing on Cluster Grids Using GIMP P. Czarnul, A. Ciereszko,
451
Benchmarking Parallel Three Dimensional FFT Kernels with ZENTURIO R. Prodan, A. Bonelli, A. Adelmann, T. Fahringer, C. Überhuber The Proof and Illustration of the Central Limit Theorem by Brownian Numerical Experiments in Real Time within the Java Applet M. Gall, R. Kutner, W. Wesela An Extended Coherence Protocol for Recoverable DSM Systems with Causal Consistency J. Brzezinski, M. Szychowiak 2D and 3D Representations of Solution Spaces for CO Problems E. Nowicki, C. Smutnicki Effective Detector Set Generation and Evolution for Artificial Immune System C. Kim, W. Kim, M. Hong
459
467
475 483
491
XLVIII
Table of Contents – Part II
Artificial Immune System against Viral Attack H. Lee, W. Kim, M. Hong
499
Proposal of the Programming Rules for VHDL Designs J. Borgosz, B. Cyganek
507
A Weight Adaptation Method for Fuzzy Cognitive Maps to a Process Control Problem E. Papageorgiou, P. Groumpos A Method Based on Fuzzy Logic Technique for Smoothing in 2D A. Çinar Proportional-Integral-Derivative Controllers Tuning for Unstable and Integral Processes Using Genetic Algorithms M.A. Paz-Ramos, J. Torres-Jimenez, E. Quintero-Marmol-Marquez Enabling Systems Biology: A Scientific Problem-Solving Environment M. Singhal, E.G. Stephan, K.R. Klicker, L.L. Trease, G. Chin Jr., D.K. Gracio, D.A. Payne
515 523
532 540
Poster Papers Depth Recovery with an Area Based Version of the Stereo Matching Method with Scale-Space Tensor Representation of Local Neighborhoods B. Cyganek
548
Symbolic Calculation for Frölicher-Nijenhuis for Exploring in Electromagnetic Field Theory J. de Cruz Guzmán, Z. Oziewicz
552
Spherical Orthogonal Polynomials and Symbolic-Numeric Gaussian Cubature Formulas A. Cuyt, B. Benouahmane, B. Verdonk
557
The Berlekamp-Massey Algorithm. A Sight from Theory of Pade Approximants and Orthogonal Polynomials S.B. Gashkov, I.B. Gashkov
561
An Advanced Version of the Local-Global Step Size Control for Runge-Kutta Methods Applied to Index 1 Differential-Algebraic Systems G. Y. Kulikov INTEGRATOR: A Computational Tool to Solve Ordinary Differential Equations with Global Error Control G. Y. Kulikov, S.K. Shindin
565
570
Table of Contents – Part II
XLIX
Reconstruction of Signal from Samples of Its Integral in Spline Subspaces J. Xian, Y. Li, W. Lin
574
The Vectorized and Parallelized Solving of Markovian Models for Optical Networks B. Bylina, J. Bylina
578
A Parallel Splitting up Algorithm for the Determination of an Unknown Coefficient in Multi Dimensional Parabolic Problem D.S. Daoud, D. Subasi
582
A-Posteriori Error Analysis of a Mixed Method for Linear Parabolic Problem M.I. Asensio, J.M. Cascón, L. Ferragut
586
Analysis of Parallel Numerical Libraries to Solve the 3D Electron Continuity Equation N. Seoane, A.J. García-Loureiro
590
Parallel Solution of Cascaded ODE Systems Applied to Experiments K. Nöh, W. Wiechert
594
A Graph Partitioning Algorithm Based on Clustering by Eigenvector T.-Y. Choe, C.-I. Park
598
Network of Networks J. de Cruz Guzmán, Z. Oziewicz
602
MSL: An Efficient Adaptive In-Place Radix Sort Algorithm F. El-Aker, A. Al-Badarneh
606
Parallel Chip Firing Game Associated with Edges Orientations R. Ndoundam, C. Tadonki, M. Tchuente
610
A Fast Multifrontal Solver for Non-linear Multi-physics Problems A. Bertoldo, M. Bianco, G. Pucci
614
Modelling of Interaction between Surface Waves and Mud Layer L. Balas
618
Computational Modelling of Pulsating Biological Flow X.S. Yang, R.W. Lewis, H. Zhang
622
Effect of Heterogeneity on Formation of Shear Zones in Granular Bodies J. Tejchman
626
L
Table of Contents – Part II
Effect of Structural Disorder on the Electronic Density of States in One-Dimensional Chain of Atoms B.J. Spisak
630
The Estimation of the Mathematical Exactness of System Dynamics Method on the Base of Some Economic System E. Kasperska,
634
Size of the Stable Population in the Penna Bit-String Model of Biological Aging K. Malarz, M. Sitarz, P. Gronek, A. Dydejczyk
638
Velocity Field Modelling for Pollutant Plume Using 3-D Adaptive Finite Element Method G. Montero, R. Montenegro, J.M. Escobar, E. Rodríguez, J.M. González-Yuste
642
Organization of the Mesh Structure T. Jurczyk,
646
Kernel Maximum Likelihood Hebbian Learning J. Koetsier, E. Corchado, D. MacDonald, J. Corchado, C. Fyfe
650
Discovery of Chemical Transformations with the Use of Machine Learning G. Fic, G. Nowak Extraction of Document Descriptive Terms with a Linguistic-Based Machine Learning Approach J. Fernández, E. Montañés, I. Díaz, J. Ranilla, E.F. Combarro
654
658
Application of Brain Emotional Learning Based Intelligent Controller (BELBIC) to Active Queue Management M. Jalili-Kharaajoo
662
A Hybrid Algorithm Based on PSO and SA and Its Application for Two-Dimensional Non-guillotine Cutting Stock Problem J.Q. Jiang, Y.C. Liang, X.H. Shi, H.P. Lee
666
Evolving TSP Heuristics Using Multi Expression Programming M. Oltean, D. Dumitrescu Improving the Performance of Evolutionary Algorithms for the Multiobjective 0/1 Knapsack Problem Using M. Oltean Genetic Evolution Approach for Target Movement Prediction S. Baik, J. Bala, A. Hadjarian, P. Pachowicz
670
674 678
Table of Contents – Part II
LI
Adaptive Transfer Functions in Radial Basis Function (RBF) Networks G.A. Hoffmann
682
Disturbance Rejection Control of Thermal Power Plant Using Immune Algorithm D.H. Kim, J.H. Cho
687
The Design Methodology of Fuzzy Controller Based on Information Granulation (IG)-Based Optimization Approach S.-K. Oh, S.-B. Roh, D.-Y. Lee
691
PID Controller Tuning of a Boiler Control System Using Immune Algorithm Typed Neural Network D.H. Kim
695
A Framework to Investigate and Evaluate Genetic Clustering Algorithms for Automatic Modularization of Software Systems S. Parsa, O. Bushehrian
699
An Artificial Immune Algorithms Apply to Pre-processing Signals W. Wajs, P. Wais
703
Identification and Control Using Direction Basis Function Neural Network M. Jalili-Kharaajoo
708
A New Dynamic Structure Neural Network for Control of Nonlinear Systems M. Jalili-Kharaajoo
713
Proposing a New Learning Algorithm to Improve Fault Tolerance of Neural Networks M. Jalili-Kharaajoo
717
Nonlinear Parametric Model Identification and Model Based Control of S. cerevisiae Production B. Akay
722
The Notion of Community in United States Computational Science Education Initiatives M.E. Searcy, J.T. Richie
726
Author Index
731
This page intentionally left blank
Table of Contents – Part IV
Workshop on Advanced Methods of Digital Image Processing The New Graphic Description of the Haar Wavelet Transform P. Porwik, A. Lisowska On New Radon-Based Translation, Rotation, and Scaling Invariant Transform for Face Recognition On Bit-Level Systolic Arrays for Least-Squares Digital Contour Smoothing J. Glasa
1
9
18
Bayer Pattern Demosaicking Using Local-Correlation Approach R. Lukac, K.N. Plataniotis, A.N. Venetsanopoulos
26
Edge Preserving Filters on Color Images V. Hong, H. Palus, D. Paulus
34
Segmentation of Fundus Eye Images Using Methods of Mathematical Morphology for Glaucoma Diagnosis R. Chrastek, G. Michelson
41
Automatic Detection of Glaucomatous Changes Using Adaptive Thresholding and Neural Networks L. Pawlaczyk, R. Chrastek, G. Michelson
49
Analytical Design of 2-D Narrow Bandstop FIR Filters P. Zahradnik,
56
Analytical Design of Arbitrary Oriented Asteroidal 2-D FIR Filters P. Zahradnik,
64
A
72
Sharing Scheme for Color Images R. Lukac, K.N. Plataniotis, A.N. Venetsanopoulos
LIV
Table of Contents – Part IV
Workshop on Computer Graphics and Geometric Modelling (CGGM 2004) Declarative Modelling in Computer Graphics: Current Results and Future Issues P.-F. Bonnefoi, D. Plemenos, W. Ruchaud
80
Geometric Snapping for 3D Meshes K.-H. Yoo, J.S. Ha
90
Multiresolution Approximations of Generalized Voronoi Diagrams I. Boada, N. Coll, J.A. Sellarès
98
LodStrips: Level of Detail Strips J.F. Ramos, M. Chover
107
Declarative Specification of Ambiance in VRML Landscapes V. Jolivet, D. Plemenos, P. Poulingeas
115
Using Constraints in Delaunay and Greedy Triangulation for Contour Lines Improvement I. Kolingerová, V. Strych,
123
An Effective Modeling of Single Cores Prostheses Using Geometric Techniques K.-H. Yoo, J.S. Ha
131
GA and CHC. Two Evolutionary Algorithms to Solve the Root Identification Problem in Geometric Constraint Solving M. V. Luzón, E. Barreiro, E. Yeguas, R. Joan-Arinyo
139
Manifold Extraction in Surface Reconstruction I. Kolingerová Expression of a Set of Points’ Structure within a Specific Geometrical Model J.-L. Mari, J. Sequeira
147
156
Effective Use of Procedural Shaders in Animated Scenes P. Kondratieva, V. Havran, H.-P. Seidel
164
Real-Time Tree Rendering I. Remolar, C. Rebollo, M. Chover, J. Ribelles
173
A Brush Stroke Generation Using Magnetic Field Model for Painterly Rendering L.S. Yeon, Y.H. Soon, Y.K. Hyun
181
Table of Contents – Part IV
LV
Reuse of Paths in Final Gathering Step with Moving Light Sources M. Sbert, F. Castro
189
Real Time Tree Sketching C. Campos, R. Quirós, J. Huerta, E. Camahort, R. Vivó, J. Lluch
197
Facial Expression Recognition Based on Dimension Model Using Sparse Coding Y.-s. Shin
205
An Application to the Treatment of Geophysical Images through Orthogonal Projections S. Romero, F. Moreno
213
A Derivative-Free Tracking Algorithm for Implicit Curves with Singularities J.F.M. Morgado, A.J.P. Gomes
221
Framework for Simulating the Human Behavior for Intelligent Virtual Agents. Part I: Framework Architecture F. Luengo, A. Iglesias
229
Framework for Simulating the Human Behavior for Intelligent Virtual Agents. Part II: Behavioral System F. Luengo, A. Iglesias
237
Point-Based Modeling from a Single Image P.-P. Vázquez, J. Marco, M. Sbert
245
Introducing Physical Boundaries in Virtual Environments P. Herrero, A. de Antonio
252
Thin Client Access to a Visualization Environment I. Fudos, I. Kyriazis
258
Interactive Visualization of Relativistic Effects with the Hardware Acceleration R. Mantiuk, K. Murawko-Wisniewska, D. Zdrojewska
264
Workshop on Computer Algebra Systems and Applications (CASA 2004) Design of Interactive Environment for Numerically Intensive Parallel Linear Algebra Calculations P. Luszczek, J. Dongarra
270
LVI
Table of Contents – Part IV
Computer Algebra for Real-Time Dynamics of Robots with Large Numbers of Joints R. Bansevicius, A. Cepulkauskas, R. Kulvietiene, G. Kulvietis
278
Development of SyNRAC—Formula Description and New Functions H. Yanami, H. Anai
286
DisCAS: A Distributed-Parallel Computer Algebra System Y. Wu, G. Yang, W. Zheng, D. Lin
295
A Mathematica Package for Solving and Displaying Inequalities R. Ipanaqué, A. Iglesias
303
Choleski-Banachiewicz Approach to Systems with Non-positive Definite Matrices with MATHEMATICA® A Closed Form Solution of the Run-Time of a Sliding Bead along a Freely Hanging Slinky H. Sarafian
311
319
Analytical Theory of Motion of a Mars Orbiter J.F. San Juan, S. Serrano, A. Abad
327
Computing Theta-Stable Parabolic Subalgebras Using LiE A.G. Noël
335
Graphical and Computational Representation of Groups A. Bretto, L. Gillibert
343
First Order ODEs: Mathematica and Symbolic-Numerical Methods C. D’Apice, G. Gargiulo, M. Rosanna
351
Evaluation of the Fundamental Physical Constants in Mathematica A.S. Siver
358
Symbolic Polynomial Interpolation Using Mathematica A. Yazici, I. Altas, T. Ergenc
364
Constant Weight Codes with Package CodingTheory.m in Mathematica I. Gashkov Graph Coloring with webMathematica Ü. Ufuktepe, G. Bacak, T. Beseri Construction of Solutions for Nonintegrable Systems with the Help of the Painlevé Test S. Y. Vernov
370 376
382
Table of Contents – Part IV
Computer Algebra Manipulations in Astronomy T. Ivanova.
LVII
388
Workshop on New Numerical Methods for DEs: Applications to Linear Algebra, Control and Engineering Higher Order Quadrature on Sparse Grids H.-J. Bungartz, S. Dirnstorfer
394
Application of Extrapolation Methods to Numerical Solution of Fredholm Integral Equations Related to Boundary Value Problems A. Sidi
402
Extrapolation Techniques for Computing Accurate Solutions of Elliptic Problems with Singular Solutions H. Koestler, U. Ruede
410
Vandermonde–Type Matrices in Two Step Collocation Methods for Special Second Order Ordinary Differential Equations S. Martucci, B. Paternoster
418
Direct Optimization Using Gaussian Quadrature and Continuous Runge-Kutta Methods: Application to an Innovation Diffusion Model F. Diele, C. Marangi, S. Ragni
426
The ReLPM Exponential Integrator for FE Discretizations of Advection-Diffusion Equations L. Bergamaschi, M. Caliari, M. Vianello
434
Function Fitting Two–Step BDF Algorithms for ODEs L. G. Ixaru, B. Paternoster
443
Pseudospectral Iterated Method for Differential Equations with Delay Terms J. Mead, B. Zubik-Kowal
451
A Hybrid Numerical Technique for the Solution of a Class of Implicit Matrix Differential Equation N. Del Buono, L. Lopez
459
A Continuous Approach for the Computation of the Hyperbolic Singular Value Decomposition T. Politi
467
LVIII
Table of Contents – Part IV
Workshop on Parallel Monte Carlo Algorithms for Diverse Applications in a Distributed Setting Using P-GRADE for Monte Carlo Computations in a Distributed Environment V.N. Alexandrov, A. Thandavan, P. Kacsuk
475
Calculating Activation Energies in Diffusion Processes Using a Monte Carlo Approach in a Grid Environment M. Calleja, M. T. Dove
483
Using Parallel Monte Carlo Methods in Large-Scale Air Pollution Modelling V.N. Alexandrov, Z. Zlatev
491
Parallel Importance Separation for Multiple Integrals and Integral Equations S. Ivanovska, A. Karaivanova
499
Investigation of the Sensitivity of the Monte Carlo Solution for the Barker-Ferry Equation with Sequential and Parallel Pseudo-Random Number Generators T.V. Gurov, P.A. Whitlock
507
Design and Distributed Computer Simulation of Thin Avalanche Photodiodes Using Monte Carlo Model M. Yakutovich
515
Convergence Proof for a Monte Carlo Method for Combinatorial Optimization Problems S. Fidanova
523
Monte Carlo Algorithm for Maneuvering Target Tracking and Classification D. Angelova, L. Mihaylova, T. Semerdjiev
531
Workshop on Modelling and Simulation of Multi-physics Multi-scale Systems Coupling a Lattice Boltzmann and a Finite Difference Scheme P. Albuquerque, D. Alemani, B. Chopard, P. Leone Accuracy versus Performance in Lattice Boltzmann BGK Simulations of Systolic Flows A.M. Artoli, L. Abrahamyan, A.G. Hoekstra
540
548
Table of Contents – Part IV
LIX
Mesoscopic Modelling of Droplets on Topologically Patterned Substrates A. Dupuis, J.M. Yeomans
556
Soot Particle Deposition within Porous Structures Using a Method of Moments – Lattice Boltzmann Approach B.F.W. Gschaider, C.C. Honeger, C.E.P. Redl
564
Numerical Bifurcation Analysis of Lattice Boltzmann Models: A Reaction-Diffusion Example P. Van Leemput, K. Lust
572
Particle Models of Discharge Plasmas in Molecular Gases S. Longo, M. Capitelli, P. Diomede
580
Fully Kinetic Particle-in-Cell Simulation of a Hall Thruster F. Taccogna, S. Longo, M. Capitelli, R. Schneider
588
Standard of Molecular Dynamics Modeling and Simulation of Relaxation in Dense Media A. Y. Kuksin, I. V. Morozov, G.E. Norman, V.V. Stegailov
596
Implicit and Explicit Higher Order Time Integration Schemes for Fluid-Structure Interaction Computations A. van Zuijlen, H. Bijl
604
Accounting for Nonlinear Aspects in Multiphysics Problems: Application to Poroelasticity D. Néron, P. Ladevèze, D. Dureisseix, B.A. Schrefler
612
Computational Modelling of Multi-field Ionic Continuum Systems J. Michopoulos Formation of Dwarf Galaxies in Reionized Universe with Heterogeneous Multi-computer System T. Boku, H. Susa, K. Onuma, M. Umemura, M. Sato, D. Takahashi
621
629
A Multi-scale Numerical Study of the Flow, Heat, and Mass Transfer in Protective Clothing M.P. Sobera, C.R. Kleijn, P. Brasser, H.E.A. Van den Akker
637
Thermomechanical Waves in SMA Patches under Small Mechanical Loadings L. Wang, R.V.N. Melnik
645
Direct and Homogeneous Numerical Approaches to Multiphase Flows and Applications R. Samulyak, T. Lu, Y. Prykarpatskyy
653
LX
Table of Contents – Part IV
Molecular Dynamics and Monte Carlo Simulations for Heat Transfer in Micro and Nano-channels A.J.H. Frijns, S.V. Nedea, A.J. Markvoort, A. A. van Steenhoven, P.A.J. Hilbers
661
Improved Semi-Lagrangian Stabilizing Correction Scheme for Shallow Water Equations A. Bourchtein, L. Bourchtein
667
Bose-Einstein Condensation Studied by the Real-Time Monte Carlo Simulation in the Frame of Java Applet M. Gall, R. Kutner, A. Majerowski,
673
Workshop on Gene, Genome, and Population Evolution Life History Traits and Genome Structure: Aerobiosis and G+C Content in Bacteria J.R. Lobry Differential Gene Survival under Asymmetric Directional Mutational Pressure P. Mackiewicz, M. Dudkiewicz, M. Kowalczuk, D. Mackiewicz, J. Banaszak, N. Polak, K. Smolarczyk, A. Nowicka, M.R. Dudek, S. Cebrat How Gene Survival Depends on Their Length N. Polak, J. Banaszak, P. Mackiewicz, M. Dudkiewicz, M. Kowalczuk, D. Mackiewicz, K. Smolarczyk, A. Nowicka, M.R. Dudek, S. Cebrat Super-tree Approach for Studying the Phylogeny of Prokaryotes: New Results on Completely Sequenced Genomes A. Calteau, V. Daubin, G. Perrieère
679
687
694
700
Genetic Paralog Analysis and Simulations S. Cebrat, J.P. Radomski, D. Stauffer
709
Evolutionary Perspectives on Protein Thermodynamics R.A. Goldstein
718
The Partition Function Variant of Sankoff ’s Algorithm I.L. Hofacker, P.F. Stadler
728
Simulation of Molecular Evolution Using Population Dynamics Modelling S. V. Semovski
736
Table of Contents – Part IV
LXI
Lotka-Volterra Model of Macro-Evolution on Dynamical Networks F. Coppex, M. Droz, A. Lipowski
742
Simulation of a Horizontal and Vertical Disease Spread in Population
750
Evolution of Population with Interaction between Neighbours A.Z. Maksymowicz
758
The Role of Dominant Mutations in the Population Expansion S. Cebrat,
765
Workshop on Computational Methods in Finance and Insurance On the Efficiency of Simplified Weak Taylor Schemes for Monte Carlo Simulation in Finance N. Bruti Liberati, E. Platen
771
Time-Scale Transformations: Effects on VaR Models F. Lamantia, S. Ortobelli, S. Rachev
779
Environment and Financial Markets W. Szatzschneider, M. Jeanblanc, T. Kwiatkowska
787
Pricing of Some Exotic Options with NIG-Lévy Input S. Rasmus, S. Asmussen, M. Wiktorsson
795
Construction of Quasi Optimal Portfolio for Stochastic Models of Financial Market A. Janicki, J. Zwierz
803
Euler Scheme for One-Dimensional SDEs with Time Dependent Reflecting Barriers T. Wojciechowski
811
On Approximation of Average Expectation Prices for Path Dependent Options in Fractional Models B. Ziemkiewicz
819
Confidence Intervals for the Autocorrelations of the Squares of GARCH Sequences P. Kokoszka, G. Teyssière, A. Zhang
827
Performance Measures in an Evolutionary Stock Trading Expert System P. Lipinski, J.J. Korczak
835
LXII
Table of Contents – Part IV
Stocks’ Trading System Based on the Particle Swarm Optimization Algorithm J. Nenortaite, R. Simutis
843
Parisian Options – The Implied Barrier Concept J. Anderluh, H. van der Weide
851
Modeling Electricity Prices with Regime Switching Models M. Bierbrauer, S. Trück, R. Weron
859
Modeling the Risk Process in the XploRe Computing Environment K. Burnecki, R. Weron
868
Workshop on Computational Economics and Finance A Dynamic Stochastic Programming Model for Bond Portfolio Management L. Yu, S. Wang, Y. Wu, K.K. Lai
876
Communication Leading to Nash Equilibrium without Acyclic Condition (– S4-Knowledge Model Case –) T. Matsuhisa
884
Support Vector Machines Approach to Credit Assessment J. Li, J. Liu, W. Xu, Y. Shi
892
Measuring Scorecard Performance Z. Yang, Y. Wang, Y. Bai, X. Zhang
900
Parallelism of Association Rules Mining and Its Application in Insurance Operations J. Tian, L. Zhu, S. Zhang, G. Huang
907
No Speculation under Expectations in Awareness K. Horie, T. Matsuhisa
915
A Method on Solving Multiobjective Conditional Value-at-Risk M. Jiang, Q. Hu, Z. Meng
923
Cross-Validation and Ensemble Analyses on Multiple-Criteria Linear Programming Classification for Credit Cardholder Behavior Y. Peng, G. Kou, Z. Chen, Y. Shi
931
Workshop on GeoComputation A Cache Mechanism for Component-Based WebGIS Y. Luo, X. Wang, Z. Xu
940
Table of Contents – Part IV
A Data Structure for Efficient Transmission of Generalised Vector Maps M. Zhou, M. Bertolotto
LXIII
948
Feasibility Study of Geo-spatial Analysis Using Grid Computing Y. Hu, Y. Xue, J. Wang, X. Sun, G. Cai, J. Tang, Y. Luo, S. Zhong, Y. Wang, A. Zhang
956
An Optimum Vehicular Path Solution with Multi-heuristics F. Lu, Y. Guan
964
An Extended Locking Method for Geographical Database with Spatial Rules C. Cheng, P. Shen, M. Zhang, F. Lu Preliminary Study on Unsupervised Classification of Remotely Sensed Images on the Grid J. Wang, X. Sun, Y. Xue, Y. Hu, Y. Luo, Y. Wang, S. Zhong, A. Zhang, J. Tang, G. Cai Experience of Remote Sensing Information Modelling with Grid Computing G. Cai, Y. Xue, J. Tang, J. Wang, Y. Wang, Y. Luo, Y. Hu, S. Zhong, X. Sun Load Analysis and Load Control in Geo-agents Y. Luo, X. Wang, Z. Xu
972
981
989
997
Workshop on Simulation and Modeling of 3D Integrated Circuits Challenges in Transmission Line Modeling at Multi-gigabit Data Rates V. Heyfitch
1004
MPI-Based Parallelized Model Order Reduction Algorithm I. Balk, S. Zorin
1012
3D-VLSI Design Tool R. Bollapragada
1017
Analytical Solutions of the Diffusive Heat Equation as the Application for Multi-cellular Device Modeling – A Numerical Aspect Z. Lisik, J. Wozny, M. Langer, N. Rinaldi
1021
Layout Based 3D Thermal Simulations of Integrated Circuits Components K. Slusarczyk, M. Kaminski, A. Napieralski
1029
LXIV
Table of Contents – Part IV
Simulation of Electrical and Optical Interconnections for Future VLSI ICs G. Tosik, Z. Lisik, M. Langer, F. Gaffiot, I. O’Conor
1037
Balanced Binary Search Trees Based Approach for Sparse Matrix Representation I. Balk, I. Pavlovsky, A. Ushakov, I. Landman
1045
Principles of Rectangular Mesh Generation in Computational Physics V. Ermolaev, E. Odintsov, A. Sobachkin, A. Kharitonovich, M. Bevzushenko, S. Zorin
1049
Workshop on Computational Modeling and Simulation on Biomechanical Engineering Inter-finger Connection Matrices V.M. Zatsiorsky, M.L. Latash, F. Danion, F. Gao, Z.-M. Li, R.W. Gregory, S. Li
1056
Biomechanics of Bone Cement Augmentation with Compression Hip Screw System for the Treatment of Intertrochanteric Fractures S.J. Lee, B.J. Kim, S.Y. Kwon, G.R. Tack
1065
Comparison of Knee Cruciate Ligaments Models Using Kinematics from a Living Subject during Chair Rising-Sitting R. Stagni, S. Fantozzi, M. Davinelli, M. Lannocca
1073
Computer and Robotic Model of External Fixation System for Fracture Treatment Y.H. Kim, S.-G. Lee
1081
Robust Path Design of Biomechanical Systems Using the Concept of Allowable Load Set J.H. Chang, J.H. Kim, B.M. Kwak
1088
A New Modeling Method for Objects with Branching Problem Using Non-uniform B-Spline H.S. Kim, Y.H. Kim, Y.H. Choe, S.-M. Kim, T.-S. Cho, J.H. Mun
1095
Motion Design of Two-Legged Locomotion Process of a Man S. Novikava, K. Miatliuk, K. Jaworek
1103
Adaptive Microcalcification Detection in Computer Aided Diagnosis H.-K. Kang, S.-M. Kim, N.N. Thanh, Y.M. Ro, W.-H. Kim
1110
Table of Contents – Part IV
LXV
Workshop on Information Technologies Enhancing Health Care Delivery The Impact of Information Technology on Quality of Healthcare Services M. Duplaga Computer Generated Patient Plans Based on Patterns of Care O.M. Winnem
1118 1126
On Direct Comparing of Medical Guidelines with Electronic Health Record J. Špidlen, D. Buchtela J. Zvárová, A. Veselý,
1133
Managing Information Models for E-health via Planned Evolutionary Pathways H. Duwe
1140
An Attributable Role-Based Access Control for Healthcare D. Schwartmann
1148
Aspects of a Massively Distributed Stable Component Space K. Schmaranz, D. Schwartmann
1156
Demonstrating Wireless IPv6 Access to a Federated Health Record Server D. Kalra, D. Ingram, A. Austin, V. Griffith, D. Lloyd, D. Patterson, P. Kirstein, P. Conversin, W. Fritsche Collaborative Teleradiology
1165
1172
Workshop on Computing in Science and Engineering Academic Programs Some Remarks on CSE Education in Germany H.-J. Bungartz The Computational Science and Engineering (CS&E) Program at Purdue University T. Downar, T. Kozlowski Adapting the CSE Program at ETH Zurich to the Bologna Process R. Jeltsch, K. Nipp
1180
1188 1196
LXVI
Table of Contents – Part IV
Computational Engineering and Science Program at the University of Utah C. DeTar, A.L. Fogelson, C.R. Johnson, C.A. Sikorski, T. Truong
1202
A Comparison of C, MATLAB, and Python as Teaching Languages in Engineering H. Fangohr
1210
Teaching Computational Science Using VPython and Virtual Reality S. Roberts, H. Gardner, S. Press, L. Stals
1218
Student Exercises on Fossil Fuels, Global Warming, and Gaia B. W. Rust
1226
Teaching Scientific Computing B.A. Shadwick
1234
Creating a Sustainable High-Performance Scientific Computing Course E.R. Jessup, H.M. Tufo
1242
CSE without Math? A First Course in Modeling and Simulation W. Wiechert
1249
Author Index
1257
High-Performance Parallel and Distributed Scientific Computing with the Common Component Architecture* David E. Bernholdt Oak Ridge National Laboratory** Oak Ridge, TN 37831-6016 USA
[email protected]
Abstract. 1 In the scientific computing community, parallel and, increasingly, distributed computing are both important paradigms for the development of large-scale simulation software. The ability to bridge seamlessly between these two paradigms is a valuable characteristic for programming models in this general domain. The Common Component Architecture (CCA)2 is a software component model specially designed for the needs of the scientific community, including support for both high-performance parallel and distributed computing. The Common Component Architecture (CCA) provides a means for software developers to manage the complexity of large-scale scientific simulations and to move toward a plug-and-play environment for highperformance computing. In the scientific computing context, component models also promote collaboration using independently developed software, thereby allowing particular individuals or groups to focus on the aspects of greatest interest to them. The CCA is being applied within an increasing range of disciplines, including combustion research, mesoscale storm prediction, global climate simulation, and computational chemistry, as well as connecting to instruments and sensors. In this talk, I will introduce the basic concepts behind component-based software engineering in general, and the common component architecture in particular. I will emphasize the mechanisms by which the CCA provides for both high-performance parallel computing and distributed computing, and how it integrates with several popular distributed computing environments. Finally, I will offer examples of several applications using the CCA in parallel and distributed contexts.
*
Research supported by the Office of Mathematical, Information and Computational Sciences (MICS) of the U.S. Dept. of Energy, Scientific Discovery through Advanced Computing (SciDAC) program. ** Oak Ridge National Laboratory is managed by UT-Battelle, LLC for the US Dept. of Energy under contract DE-AC-05-00OR22725. 1 This is the abstract of an invited talk for the Programming Grids and Metasystems Workshop. 2 For more information, please see http://www.cca-forum.org M. Bubak et al. (Eds.): ICCS 2004, LNCS 3038, p. 1, 2004. © Springer-Verlag Berlin Heidelberg 2004
Multiparadigm Model Oriented to Development of Grid Systems 1
1
Jorge Luis Victória Barbosa , Cristiano André da Costa , Adenauer Corrêa Yamin2, and Cláudio Fernando Resin Geyer3 1
Informatics Department, University of Vale do Rio dos Sinos São Leopoldo, RS, Brazil {barbosa,cac}@exatas.unisinos.br
2
Informatics Department, Catholic University of Pelotas (UCPel) Pelotas, RS, Brazil
[email protected]
3
Informatics Institute, Federal University of Rio Grande do Sul (UFRGS) Porto Alegre, RS, Brazil
[email protected]
Abstract. Multiparadigm approach integrates programming language paradigms. We propose Holoparadigm (Holo) as a multiparadigm model oriented to development of grid systems. Holo uses a logic blackboard (called history) to implement a coordination mechanism. The programs are organized in levels using abstract entities called beings. First, we describe the principal concepts of the Holoparadigm. After, the principles of a language based on the Holoparadigm are presented. Besides, we propose the Grid Holo (GHolo), a platform to support the multi-domain heterogeneous distributed computing of programs developed in Holo. GHolo is based on object mobility and blackboards. This distributed model can be fully implemented on Java platform. Keywords: Multiparadigm, Mobility, Blackboard and Grid Systems.
1 Introduction Several programming language paradigms were developed to make computer programming more effective. There is no ideal solution since each one has advantages and disadvantages. Multiparadigm approaches mix two or more basic paradigms trying to get a more powerful and general solution and to overcome the specific limitations of each paradigm taking advantage of its most useful characteristics. Several multiparadigm languages and environments have been proposed as for example [3, 12, 18, 20, 23]. Each paradigm has sources of implicit parallelism, for example, AND parallelism and OR parallelism in logic programming [4, 27]. Another example is object-oriented paradigm that allows the exploitation of inter-object parallelism and intra-object parallelism [9, 21]. The multiparadigm approach integrates paradigms. So, it also integrates their parallelism sources. In this context, interest in automatic exploitation of parallelism in multiparadigm software has emerged. The development of distributed software using multiparadigm models has M. Bubak et al. (Eds.): ICCS 2004, LNCS 3038, pp. 2–9, 2004. © Springer-Verlag Berlin Heidelberg 2004
Multiparadigm Model Oriented to Development of Grid Systems
3
received attention of the scientific community [9, 13, 14, 21, 25] with some systems considering mobility, heterogeneous hardware and cluster architectures. In this paper we propose Holoparadigm (Holo) as a multiparadigm model oriented to development of grid systems. A logic blackboard (called history) implements the coordination mechanism and a new programming entity (called being) organizes the several encapsulated levels of beings and histories (multi-domains). A new multiparadigm language (Hololanguage) implements the main ideas introduced by Holoparadigm. Besides, we propose a platform to support the distributed execution of programs developed in Holo. This platform is called Grid Holo (GHolo). GHolo has a heterogeneous network as physical execution environment and is based on object mobility, blackboards and multi-domain organization (tree of beings). A prototype was implemented using Java [17] and special libraries to support mobility (Voyager [28]) and blackboards (Jada [10]). The paper is organized in five sections. Section two presents the Holoparadigm and the Hololanguage. In section three is proposed the Grid Holo. Section four describes related works. Finally, section five draws some conclusions and presents directions for future works.
2 Holoparadigm and Hololanguage Being is the main Holoparadigm abstraction. There are two kinds of beings: elementary being (atomic being without composition levels) and composed being (being composed by other beings). An elementary being (figure 1a) is organized in three parts: interface, behavior and history. The interface describes the possible interactions between beings. The behavior contains actions, which implement functionalities. The history is a shared storage space in a being. A composed being (figure 1b) has the same organization, but may be composed by others beings (component beings). Each being has its history. The history is encapsulated in the being. In composed being, the history is shared by component beings. Several levels of encapsulated history can possibly exist. A being uses the history in a specific composition level. For example, figure 1c shows two levels of encapsulated history in a being with three composition levels. Behavior and interface parts are omitted for simplicity. Automatic distribution is one of the main Holoparadigm goals. Figure 2 exemplifies a possible distribution of the being presented in the figure 1b. Besides that, the figure presents the mobility in Holo. The being is distributed in two nodes of the distributed architecture. The history of a distributed being is called distributed history. This kind of history can be implemented using DSM techniques [24] or distributed shared spaces [2, 10, 11]. Mobility [16] is the dislocation capacity of a being. In Holo, there are two kinds of mobility: logical mobility (being is moved when crosses one or more borders of beings) and physical mobility (dislocation between nodes of distributed architectures). Figure 2 exemplifies two possible mobilities in the being initially presented in the figure 1b. After the dislocation, the moveable being is unable to contact the history of the source being (figure 2, mobility A). However, now the being is able to use the history of the destiny being. Here, physical mobility only occurs if the source and destiny beings are in different nodes of the distributed architecture (it is the case in
4
J.L.V. Barbosa et al.
Fig. 1. Being organization
Fig. 2. Distributed being and mobility
our example). Logical and physical mobilities are independent. Occurrence of one does not imply in the occurrence of the other. For example, the mobility B in the figure 2 is a physical mobility without logical mobility. In this example, the moved being does not change its history view (supported by the blackboard). This kind of situation could happen if the execution environment aims to speedup execution through locality exploitation. The coordination model used in Holo is based on the blackboard architecture [22] (figure 3a). A blackboard is composed by a common data area (blackboard) shared by a collection of programming entities called knowledge sources (KSs). Control is implicit in the blackboard access operations. The read and write operations in the blackboard are used to communication and synchronization between KSs. This kind of control is called implicit invocation. A composed being architecture is similar to the blackboard architecture, since several components share a common data area. In Holo, KSs are beings and the blackboard is the history. Since blackboard implicit
Multiparadigm Model Oriented to Development of Grid Systems
5
Fig. 3. Holo coordination model
invocation has several limitations, explicit invocation was introduced in the coordination model. Explicit invocation is any direct call between entities. So, the beings influence the others using the history, but can change information directly too. Figure 3b shows the Holo coordination model. History is a logic blackboard, i.e., the information stored is a group of logic terms. Interaction with the history uses two kinds of Linda-like [8] operations: affirmation and question. An affirmation puts terms in the history, like asserts in Prolog databases. Moreover, a question permits to consult terms from the history. A consult does a search in the database using unification of terms. A question is blocking or non-blocking. A blocking question only returns when a unifying term is found. Therefore, blocking questions synchronize beings using the implicit invocation. In a non-blocking question, if a unifying term is not found, the question immediately fails. Besides that, a question is destructive or non-destructive. A destructive question retracts the unifying term. The non-destructive one does not remove it. Hololanguage (so-called Holo) is a programming language that implements the concepts of Holoparadigm. A program is composed by descriptions of beings. The language supports logical mobility and concurrency between actions of a being. Besides that, the Hololanguage permits both kinds of blackboard interaction proposed by the Holoparadigm. Five kinds of actions are supported: (1) logic action (LA) is a logic predicate; (2) imperative action (IA) is a group of imperative commands; (3) modular logic action (MLA) contains several logic actions encapsulated in a module; (4) modular imperative action (MIA) encapsulates several imperative actions; (5) multiparadigm action (MA) integrates logic and imperative actions. Actions are composed using an Action Composition Graph (ACG). Following the Peter Wegner’s opinion [29] about the impossibility of mixing logic and imperative behaviors, we have created the Action Invocation Graph (AIG). This graph determines the possible order of action calls during a program execution. MAs, IAs and MIAs call any action. LAs and MLAs only call LAs and MLAs. Therefore, there are two regions of actions during an execution, namely, imperative and logic regions. If an execution flow goes in the logic region, the only way to return to the imperative region is finishing the flow (returning the results asked from the imperative region). This methodology eliminates many problems, which emerge when logic and imperative commands are mixed (for example, distributed backtracking [5]). We believe AIG is an important contribution to the discussion presented by Wegner [29, 30].
6
J.L.V. Barbosa et al.
3 Grid Holo Holo to grid systems is called Grid Holo (GHolo). The being multi-level organization (see figure 1c) is adequate to modelling heterogeneous multi-domain distributed systems. Holo was created to support implicit distribution, i.e., automatic exploitation of distribution using mechanisms provided by basic software (compiler and execution environment). Holoparadigm abstractions are hardware independent. However, the model is dedicated to distributed architectures. When the hardware is distributed, there are two main characteristics to be considered: (1) mobility support: it is necessary to implement the physical mobility treatment when there is a move to a being located in another node; (2) dynamic and hierarchical history support: distribution involves data sharing between beings in different nodes (distributed history). There are several levels of history (hierarchical history). Besides that, access history is adapted during the execution to support the mobility (dynamic history). GHolo is the software layer that supports the grid distributed computing of programs in Holo. It creates support to physical mobility and dynamic/hierarchical history in a grid. GHolo project is based on a structure called Tree of Beings (HoloTree, see figure 4). This structure is used to organize a being during its execution. The tree organizes the beings in levels. A being only can access the history of the composed being to which it belongs. This is equivalent to access the history of being localized in the superior level. A logical mobility is implemented moving a leaf (elementary being) or a tree branch (composed being) from the source being to the destiny being. The Jada spaces [10] are used to support the change of context. After the mobility, the being moved has direct access to the destiny being’s space.
Fig. 4. Grid Holo (distributed HoloTree)
The figure 4 presents the GHolo architecture to the being initially shown in the figure 2. The figure shows the HoloTree distributed in two nodes. The changes to both mobilities of figure 2 are demonstrated. Each being is implemented using an object and a Jada space (history). GHolo initialization involves the creation of a Voyager-enabled program [28] (Voyager environment) in each node that will be used. Since Voyager executes on the Java Virtual Machine each node will also have a running JVM. During the initialization, a Table Environment (TE) indicates the nodes
Multiparadigm Model Oriented to Development of Grid Systems
7
that will be used by GHolo. During a program execution, if a logical mobility results in a physical mobility, it executes a moveTo operation in Voyager (mobility A, figures 2 and 4). When a physical mobility is realized without logical mobility (mobility B, figures 2 and 4), the tree of beings does not change, but a moveTo operation is realized. This kind of mobility does not have any kind of relation with the program. It is a decision of the environment to support a specific functionality (load balancing, tolerance fault, etc). GHolo does not support this kind of decision yet, but there is on going work in this subject [31].
4 Related Works There are other multiparadigm implementations over distributed environment. model [21] supports the distribution of objects, which implement methods using functions (functional classes) and predicates (logic classes). The implementation is based on the translation of functional classes into Lazy ML (LML) modules and translation of logic classes into Prolog modules. The distributed architecture is a network of Unix workstations using 4.3 BSD sockets to implement message passing. The runtime environment was initially implemented using C language, Quintus Prolog and LML. In a second phase, programs were only translated into C language. does not focus mobility. In addition, none kind of shared space is supported between objects. Ciampolini et al [9] have proposed DLO, a system to create distributed logic objects. This proposal is based on previous works (Shared Prolog [7], ESP [11] and ETA [2]). The implementation is based on the translation of DLO programs into clauses of a concurrent logic language called Rose [6]. The support to Rose execution is implemented on a MIMD distributed memory parallel architecture (transputerbased Meiko Computing Surface). The runtime environment consists of a parallel abstract machine that is an extension of the WAM [1]. This proposal does not support mobility and it is not applied on a network of workstations. DLO does not support levels of spaces. Oz multiparadigm language [20] is used to create a distributed platform called Mozart [25]. Oz uses a constraint store similar to a blackboard and supports the use of several paradigm styles [15, 20]. Besides, Mozart has special support to mobility of objects [13] and distributed treatment of logic variables [14]. Mozart distributed architecture is a network of workstations providing standard protocols such as TCP/IP. The runtime environment is composed by four software layers [25]: Oz centralized engine (Oz virtual machine [19]), language graph layer (distributed algorithms to decide when to do a local operation or a network communication), memory management layer (shared communication space and distributed garbage collection) and reliable message layer (transfer of byte sequences between nodes). The physical mobility supported by Mozart is completely transparent, i. e., the system decides when to move an object. None kind of logical mobility is used. The shared spaced supported by Mozart is monotonic and stores constraints, while Holo being’s history is a non-monotonic logic blackboard that stores logic tuples (terms). In addition, Mozart does not provide levels of encapsulated contexts composed by objects accessing a shared space.
8
J.L.V. Barbosa et al.
Tarau has proposed Jinni [26], a logic programming language that supports concurrency, mobility and distributed logic blackboards. Jinni is implemented using BinProlog [5] a multi-threaded Prolog system with ability to generate C/C++ code. Besides that, it has special support to Java, such as a translator allowing packaging of Jinni programs as Java classes. Jinni is not a multiparadigm platform. In addition, Jinni does not work with logical mobility and with levels of encapsulated blackboards. So, Oz and Jinni have a kind of mobility. In addition, they can be executed over network of workstations. However, we believe that the support to hierarchy of spaces as proposed by Holo is an innovation.
5 Conclusion We have proposed the use of Holo to multi-domain heterogeneous systems. Holoparadigm concepts estimulate the grid programming. Besides, we proposed the Grid Holo (GHolo), namely, an environment to grid computing that automatically manages the tree of beings distribution. One important aspect of Holo is the coordination model, which simplifies the management of mobility. For this coordination, the Holo model uses a logic blackboard while GHolo proposes the use of spaces to implement it. Another important concept is the autonomous management of mobility. Holo model does not deal with physical distribution so mobility is always at logic level, i.e., between beings. GHolo execution environment can define what kind of mobility is necessary: a logical or a physical one. A logical mobility requires changes in history sharing, while physical also involves objects mobility. Future works will improve our proposal. One ongoing work [31] aims to propose a dynamic scheduling of distributed objects, which can be directly used in GHolo. Optimizations over initial execution kernel are also under development.
References 1. 2. 3. 4. 5. 6.
Ait-Kaci, H. Warren’s Abstract Machine– A Tutorial Reconstruction. MIT Press, 1991. Ambriola, V.; Cignoni, G. A.; Semini; L. A Proposal to Merge Multiple Tuple Spaces, Object Orientation and Logic Programming. Computer Languages, Elmsford, v.22, n.2/3, p.79-93, July/October 1996. Apt, R. et al. Alma-0: An Imperative Language that Supports Declarative Programming. ACM Transactions on Programming Languages and Systems, New York, v.20, September 1998. Barbosa, J. L. V.; Vargas, P. K.; Geyer, C. GRANLOG: An Integrated Granularity Analysis Model for Parallel Logic Programming. Workshop on Parallelism and Implementation Technology (constraint) Logic Programming, London, 2000. Bosschere, K.; Tarau, P. Blackboard-based Extensions in Prolog. Software – Practice and Experience, v.26, n.1, p.49-69, January 1996. Brogi, A. AND-parallelism without shared variables. Seventh International Conference on Logic Programming. MIT Press, p.306-324, 1990.
Multiparadigm Model Oriented to Development of Grid Systems 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31.
9
Brogi, A.; Ciancarini, P. The Concurrent Language, Shared Prolog. ACM Transaction on Programming Languages and Systems. New York, v.13, n.1, p.99-123, January 1991. Carriero, N.; Gelernter, D. Linda in context. Communications of the ACM, v.32, n.4, p.444-458, 1989. Ciampolini, A.; Lamma, E.; Stefanelli, C; Mello, P. Distributed Logic Objects. Computer Languages, v.22, n.4, p.237-258, December 1996. Ciancarini, P.; Rossi, D. JADA: A Coordination Toolkit for Java. http://www.cs.unibo.it/~rossi/jada, 2003. Ciancarini, P. Distributed Programming with Logic Tuple Spaces. New Generating Computing, Berlin, v.12, n.3, p.251-283,1994. Hanus, M. The Integration of Functions into Logic Programming from Theory to Practice. Journal of Logic Programming, New York, v.19/20, p.583-628, May/July 1994. Haridi, S. et al. Programming Languages for Distributed Applications. New Generating Computing, v.16, n.3, p.223-261,1998. Haridi, S. et al. Efficient Logic Variables for Distributed Computing. ACM Transactions on Programming Languages and Systems, v. 21, n.3, p.569-626, May 1999. Henz, M. Objects in Oz. Saarbrüchen: Universität des Saarlandes, May 1997. (PhD Thesis) IEEE Transactions on Software Engineering, v.24, n.5, May 1998. (Special Issue on Mobility) Java. http://www.sun.com/java, 2003 Lee, J. H. M.; Pun, P. K. C. Object Logic Integration: A Multiparadigm Design Methodology and a Programming Language. Computer Languages, v.23, n.1, p.25-42, April 1997. Meh, M.; Scheidhauer, R.; Schulte, C. An Abstract Machine for OZ. Seventh International Symposium on Programming Languages, Implementations, Logics and Programs (PLIP’95), Springer-Verlag, LNCS, September 1995. Muller, M.; Muller, T.; Roy, P. V. Multiparadigm Programming in Oz. Visions for the Future of Logic Programming: Laying the Foundations for a Modern Successor of Prolog, 1995. Ng, K. W.; Luk, C. K. I+: A Multiparadigm Language for Object-Oriented Declarative Programming. Computer Languages, v.21, n.2, p. 81-100, July 1995. Nii, H. P. Blackboard systems: the blackboard model of problem solving and the evolution of blackboard architectures. AI Magazine, v.7, n.2, p.38-53,1986. Pineda, A.; Hermenegildo, M. O’CIAO: An Object Oriented Programming Model Using CIAO Prolog. Technical report CLIP 5/99.0 , Facultad de Informática, UMP, July 1999. Proceedings of the IEEE, v.87, n.3, march 1999. (Special Issue on Distributed DSM) Roy, P. V. et al. Mobile Objects in Distributed Oz. ACM Transactions on Programming Languages and Systems, v.19, n.5, p.804-851, September 1997. Tarau, P. Jinni: Intelligent Mobile Agent Programming at the Intersection of Java and Prolog. PAAM’9, The Practical Applications Company, 1999. Vargas, P. K.; Barbosa, J. L. V.; Ferrari, D.; Geyer, C. F. R.; Chassin, J. Distributed OR Scheduling with Granularity Information. XII Symposium on Computer Architecture and High Performance Computing, Brazil, 2000. Voyager. http://www.recursionsw.com/products/voyager/voyager.asp, 2003 Wegner, P. Tradeoffs between Reasoning and Modeling. In: Agha, G.; Wegner, P.; Yonezawa, A. (eds.). Research Direction in Concurrent Object-Oriented Programming. Mit Press, p.22-41, 1993. Wegner, P. Why interaction is more powerful than algorithms. Communications of the ACM, v. 40, n. 5, p.80-91, May 1997. Yamin, A. C. ExEHDA: Execution Environment for High Distriubted Applications. PPGC/UFRGS, 2001. (PHD proposal)
The Effect of the Generation Clusters: Changes in the Parallel Programming Paradigms Jari Porras, Pentti Huttunen, and Jouni Ikonen Lappeenranta University of Technology, Lappeenranta, FIN-53100, Finland {Jari.Porras,Pentti.Huttunen,Jouni.Ikonen}@lut.fi
Abstract. Programming paradigms for networks of symmetric multiprocessor (SMP) workstation generation of clusters) are discussed and a new paradigm is introduced. The SMP cluster environments are explored in regard to their advantages and drawbacks with a special focus on memory architectures and communication. The new programming paradigm provides a solution to write efficient parallel applications for the generation of clusters. The paradigm aims at improving the overlap of computation and communication and the locality of communication operations. The preliminary results with large message sizes indicate improvements in excess of 30% over traditional MPI implementations.
1
Introduction
The main goal of utilizing a parallel computing environment is, most likely, the need to increase the performance of time-critical applications. There are numerous factors that impact the overall performance of a parallel application such as the number of processors, the memory architecture, and communication between processors to name a few. In order to maximize the performance of a parallel system all factors have to be considered and an optimal balance must be found. This paper discusses the latest trends in parallel computing environments. The study shows that a new environment has emerged. This new environment is a successor of a network of workstations where each workstation consists of one processor. The generation of clusters is composed of workstations that have two or more processors. Furthermore, such systems generally pose a more heterogeneous execution environment due to various hardware and software components found in them. The new parallel environment requires changes in traditional programming paradigm or entirely new programming paradigms to efficiently utilize the available resources. This paper discusses requirements for programming paradigms for generation clusters, and describes an implementation of a communication library (MPIT) that supports the special features of SMP clusters, such as multilevel memory architecture.
M. Bubak et al. (Eds.): ICCS 2004, LNCS 3038, pp. 10–17, 2004. © Springer-Verlag Berlin Heidelberg 2004
The Effect of the
2
Generation Clusters
11
Developments in Parallel Environments
Parallel environments have developed significantly during the past few years as processor and network technologies have evolved. Presently, the environments can be divided into the following categories:
2.1
Symmetric Multiprocessors (SMP)
In SMP machines the processors are connected through an internal network in such a way that all processors have equal access to the local (global) memory. Communication between processors occurs through this memory. Therefore, the communication is expedient, but can suffer from congestion on the network. Current multiprocessor PCs represent this category of parallel systems.
2.2
Clusters or Networks of Workstations (NOW)
Clusters are environments where processors are physically separated into different workstations and the workstations are connected through a network. The popularity of these environments is often contributed to the significant improvement in the performance-to-cost ratio compared to proprietary parallel systems. However, these environments introduce additional complexity to programming and running of parallel applications. This is a result of the distributed memory architecture and the external communication network. Together, these two characteristics introduce latencies to memory access and to communication between processors. For the purpose of this paper, the networks of single processor workstations (such as Beowulf clusters) are denoted as generation of the clusters.
2.3
Clusters of SMP Machines
Due to the low cost of multiprocessor workstations, clusters of SMP workstations have seen a considerably increased in number [3]. The workstations are connected in a similar way than in the traditional cluster environments but each node is a symmetric multiprocessor workstation with two or more processors. Therefore, the communication can occur internally or externally depending on the location of source and destination processors. An SMP cluster is denoted as a generation cluster.
3
Changes in the Parallel Programming Paradigms
Programming paradigms for parallel environments commonly consists of a communication library to allow processors to exchange messages. In fact, most popular programming paradigms, such as MPI [10] and PVM [5], are merely message passing libraries. The communication introduces overhead to parallel applications, and thus must be carefully implemented to minimize its contribution.
12
J. Porras, P. Huttunen, and J. Ikonen
Fig. 1. The four levels of programmability in parallel systems.
There are various programming paradigms to write parallel applications based on the environment in which the applications are run. Fig. 1 depicts the paradigms and their main characteristics. At the lowest level, parallelism occurs within a processor through the Hyperthreading technology [9]. Hyperthreading is the simplest approach from the programmer’s point of view as the parallelization is automatically performed by the processors. The communication is handled implicitly through the shared memory (or even registers). The utilization of user-level threads in an SMP workstation represents the second level in Fig. 1. The programmer must be familiar with the thread-programming paradigm to efficiently implement a parallel application. Since the processors are still within a single workstation in an SMP environment, the communication between the processors occurs via the shared memory. In the generation of clusters the memory architecture is distributed. Therefore, the environment requires messages to be transferred from one workstation to another with a help of a communication library such as MPI [10] or PVM [5]. The generation of clusters combine the SMP and traditional cluster environments by incorporating shared and distributed memory environments. Thus, a new paradigm is required in order to fully utilize the available resources and to obtain maximum performance. Finally, the top level in Fig. 1 illustrates an environment that integrates (SMP) clusters to each other to form grids. The grids add another level of message passing as communication between clusters is necessitated.
4
New 2-Level Communication Paradigm
The 2-level programming paradigm introduced in this section is not novel per se, since several studies have been conducted on 2-level communication paradigms: 1. Multithreaded and thread-safe MPI implementations have been proposed in [1], [2], [11], [12], [14], [15] 2. Hybrid models with MPI and OpenMP have been studied in [4], [6], [7], [8], [13]
The Effect of the
Generation Clusters
13
The programming paradigm, MPIT, developed by the authors is a communication library built on top of MPI. The library provides functions to handle MPI operations in a thread-safe manner. MPIT considers both intra and inter workstation communication by using shared memory and message passing according to the resources available. The POSIX threads are used to run instances of the code on processors in a workstation. The intra workstation communication among threads is handled through the shared memory. The message passing is based on the MPI library and used only in inter workstation communication. The determination of whether shared memory or message passing is utilized is done automatically within the library. An MPIT application operates in a single process on a workstation regardless of the number of processors. This process is created when the MPI environment is initialized through a 3rd party software (such as mpirun). The MPI environment must be initialized prior to calling the MPIT initialization function. The initialization of the MPIT library consists of the creation of the communication and the worker threads and local message buffers. The communication thread is responsible for handling all incoming and outgoing messages from a process (i.e. workstation), whereas worker threads execute the actual code. In addition to the initialization and termination functions, the MPIT library provides a set of communication routines. The routines are very similar to the standard MPI communication operations. As a matter of fact, the only difference is that the MPIT routines have an additional argument, the target thread id. The target thread identifier allows for messages to be sent to a specific thread on a workstation rather than merely to the workstation. However, if the thread identifier is not defined, the message is sent to the workstation and processed by any of the worker threads on that workstation. Analogous to MPI, there are blocking and non-blocking send and receive operations available. Also, MPIT provides various thread manipulation routines. These routines allow the programmer to control the number of worker threads on a workstation and the execution of the threads. With the help of the thread manipulation routines, the programmer is capable of adjusting the load imposed by the MPIT application on the workstation; more threads can be created, if the load on the workstation is low, whereas existing threads can be terminated to lower the impact of the MPIT application on the workstation’s resources. The remaining thread manipulation routines are related to synchronization. There are barrier synchronization routines as well as routines to control the execution of a single thread. Aspects like scheduling and load balancing can be addressed by this approach. The communication thread can be instructed to perform scheduling and load balancing operations to dynamically adjust loads on workstations or to retrieve new work for the workstation. This feature provides automatic scheduling functionality that occurs simultaneously with the execution of the worker threads. Therefore, the proposed programming paradigm supports not only the overlap of communication and computation but also the overlap of scheduling/load balancing and computation. The support for the scheduling/load balancing and
14
J. Porras, P. Huttunen, and J. Ikonen
computation overlap is very important in heterogeneous and non-dedicated generation clusters due to the necessity of frequent scheduling and load balancing operations. The MPIT programming paradigm also provides a mechanism to assign priorities to the threads executed in a workstation. With this priority scheme a preference may be given either to the communication thread or the worker threads. Thus, it provides the means for the paradigm to adapt to the needs of the application and to the requirements set by the underlying network. For example, in an application where a large number of messages need to be exchange, the communication thread should be assigned with a higher priority than the worker threads. This allows for the communication operations to occur practically instantly minimizing the overhead introduced by the communication. A reversed priority scheme is applicable when there is no need for constant communication.
5
Performance
The MPIT library was tested in a cluster of 4 dual processor workstations. Table 1 shows the configuration of the workstations.
In order to estimate the performance of the MPIT library, a new benchmark was implemented. This benchmark makes it possible to evaluate the MPIT performance with various processor topologies, messaging schemes, and message types and sizes. The benchmark configuration for the preliminary results shown in this paper was as follows: the benchmark had 2 phases, computation and communication. During the computation phase each processor spent 1 second in a busy-wait loop, after which the process sent and received a message. The processor topology was a ring, in which each processor send a message to its right neighbor and received a message from its left neighbor. The performance of MPI and MPIT were compared with 2 cluster configurations. The results shown in Fig. 2 illustrate three different cases of where one processors of all 4 workstations were used. In the dedicated system no other user processes were run, whereas in two other scenarioes 1 and 3 CPUs on different workstations were executing other user processes. As all the processes were distributed among the workstations all communication operations involved the Myrinet network. The results clearly indicate that a simple MPI application is faster when the message size is below 16KB. However, the MPIT application provides up to 30%
The Effect of the
Generation Clusters
15
Fig. 2. Performance gain/loss of the MPIT library with 4 processes (1 process per workstation).
increase in the performance with message sizes greater than 16KB. The significant diffences with small message sizes is explained by the short message transfer times, whereas their impact becomes more apparent with the large message sizes. In addition, the current implementation of the MPIT library incurs unnecessary overhead when a message is sent synchronously to a remote process. This is due to a fact the communication thread is involved in the transmission even though it is not mandatory. This issue will be solved in the next release of the software. The performance improvement over the MPI application can be contributed to the overlap of computation and communication. The overlap allows processors to continue their execution immediately after initiating a communication operation. This also leads to a more synchronized execution of the processes which minimizes wait times during the communication phases. The second test included running the benchmark on all available 8 processors on the test cluster. The test was run only in the dedicated mode where no other user processes were running. The results are shown in Fig. 3. The figure also entails the results from the dedicated 4 processor test for comparison purposes. Again, the MPI application has the advantage over the MPIT library with message sizes smaller than 16KB. With larger message sizes, the MPIT library has significant better performance than MPI. Furthermore, the MPIT performance has improved slightly compared to the 4 processor test. These preliminary results indicate that MPIT has the potential to provide superior performance than MPI. However, at this point, MPI outperforms MPIT
16
J. Porras, P. Huttunen, and J. Ikonen
Fig. 3. Performance gain/loss of the MPIT library with 4 and 8 processes (1 process per workstation) in dedicated systems.
with small message sizes. As earlier discusses, the next release of the MPIT code will include an improved transmission mechanism for small messages, which should allow MPIT to excel regardless of the message size.
6
Conclusions
In this paper programming paradigms for cluster of SMP workstations were discussed. Also, a new programming paradigm, implemented as a thread-safe communication library on top of MPI, was introduced. The library, MPIT, optimizes the communication within and between the workstations of the cluster. It is important to realize that MPIT does not require any changes to the actual MPI implementation. The performance results obtained show that an implementation like MPIT is required order to take full advantage of the generation clusters. Although, the performance of MPIT was inferior to MPI with small message sizes, it outpermed MPI with large message sizes (16KB and up). The new release of the MPIT library will include a new design for the transmission of small messages. Overall, the preliminary results are very encouraging as nearly 40% improvements over MPI were observed on a cluster of dual processor workstations. In addition to the new communication scheme, MPIT includes features to perform automatic scheduling and load balancing, and to prioritize execution of
The Effect of the
Generation Clusters
17
communication and worker threads. In fact, as MPIT encompasses all these feature it could be extended for use in GRID environments where communication, load balancing, and scheduling are even further more complex issues than in generation clusters.
References 1. Bader, D.A., Jájá, J.: SIMPLE: A Methodology for Programming High Performance Algorithms on Clusters of Symmetric Multiprocessors (SMPs). Journal of Parallel and Distributed Computing 58 (1999) 92–108 2. Chowdappa, A.K., Skjellum, A., Doss, N.E.: Thread-Safe Message Passing with P4 and MPI. Technical Report TR-CS-941025, Computer Science Department and NSF Engineering Research Center, Mississippi State University (1994) 3. Clusters@TOP500 list. http://clusters.top500.org 4. Djomehri, M.J., Jin, H.H.: Hybrid MPI+OpenMP Programming of a Overset CFD Solver and Performance Investigations. NAS Technical Report NAS-02-002 (2002) 5. Geist A. et. al.: PVM: Parallel Virtual Machine. MIT press, 1994. 6. He, Y., Ding, C.H.Q.: MPI and OpenMP Paradigms on Clusters of SMP Architectures: the Vacancy Tracking Algorithm for Multi-Dimensional Array. 7. Hu, Y., Lu, H., Cox, A. and Zwaenepoel, W.: OpenMP for Networks of SMPs. Journal of Parallel and Distributed Computing 60 (2000) 1512–1530 8. Kee, Y-S., Kim, J-S., Ha, S.: ParADE: An OpenMP Programming Environment for SMP Cluster Systems. Proceedings of Supercomputing 2003 (2003) 9. Leng, T., Ali, R., Hsieh, J., Mashayekhi, V., Rooholamini, R.: An Empirical Study of Hyper-Threading in High Performance Computing Clusters. Proceedings of LCI International Conference on Linux Clusters: The HPC Revolution 2002 (2002) 10. Pancheco, P.: Parallel Programming with MPI. Morgan Kaufmann (1997). 11. Protopopov, B. Skjellum A.: A multithreaded message passing interface (MPI) Architecture: Performance and Program Issues. Journal of Parallel and Distributed Computing 61 (2001) 449–466 12. Rauber, T., Runger, G., Trautmann, S.: A Distributed Hierarchical Programming Model for Heterogeneous Cluster of SMPs. Proceedings of the International Parallel and Distributed Processing Symposium (2003) 381–392 13. Smith, L., Bull, M.: Development of mixed mode MPI / OpenMP Applications. Scientific Programming 9 (2001) 83–98 14. Tang, H., Yang, T.: Optimizing Threaded MPI Execution on SMP Clusters. Proceedings of Supercomputing 2001 (2001) 381–392 15. Tang, H., Shen, K., Yang, T.: Compile/Run-time Support for Threaded MPI Execution on Multiprogrammed Shared Memory Machines. Proceedings of Programming Principles of Parallel Processing (1999) 107–118
JavaSymphony, a Programming Model for the Grid* Alexandru Jugravu1 and Thomas Fahringer2 1
University of Vienna, Institute for Software Science, Liechtensteinstr. 22, A-1090 Wien, Austria 2 University of Innsbruck, Institute for Software Science, Technikerstr. 25/7, A-6020 Innsbruck, Austria
Abstract. In previous work, JavaSymphony has been introduced as a high level programming model for performance-oriented distributed and parallel Java programs. We have extended JavaSymphony to simplify the development of Grid applications written in Java, allowing the programmer to control parallelism, load balancing, and locality at a high level of abstraction. In this paper, we introduce new features to support the widely popular workflow paradigm. The overall idea is to provide a high level programming paradigm that shields the programmer from low level implementation details such as RMI, sockets, and threads. Experiments will be shown to demonstrate the usefulness of JavaSymphony as a programming paradigm for the Grid.
1 Introduction Numerous research projects have introduced class libraries or language extensions for Java to enable parallel and distributed high-level programming. However, most approaches tend towards automatic management of locality, parallelism and load balancing which is almost entirely under the control of the runtime system. Automatic load balancing and data migration can easily lead to performance degradation. JavaSymphony, on the other hand, is a programming paradigm for wide classes of heterogeneous systems that allows the programmer to control locality, parallelism and load balancing at a high level of abstraction. In previous work, we describe the JavaSymphony programming paradigm[1], implementation[2] and we evaluate the usefulness of our system for several parallel and distributed applications[3]. In this paper we describe important JavaSymphony mechanisms for controlling parallelism, load balancing, and locality, which are crucial for the Grid. Moreover, we introduce new features to simplify the development of Grid workflow applications at a high level, including a user interface to build the graphical representation of a workflow process, an XML-based description language for workflow applications, library support for the definition of *
This research is partially supported by the Austrian Science Fund as part of Aurora Project under contract SFBF1104.
M. Bubak et al. (Eds.): ICCS 2004, LNCS 3038, pp. 18–25, 2004. © Springer-Verlag Berlin Heidelberg 2004
JavaSymphony, a Programming Model for the Grid
19
the workflow and its components, and a specialized scheduler for workflow applications. We describe the components of our workflow model, which includes activities, links, conditional branches, and loops. We also demonstrate these features for an existing JavaSymphony application, which is suitable to be modelled by using a workflow. The rest of this paper is organized as follows. The next section discusses related work. In Section 3 we briefly introduce the main features of the JavaSymphony programming paradigm, showing also how they are related to Grid computing. Section 4 presents the new framework for developing JavaSymphony workflow applications, and illustrates an experiment to translates an existing application into a workflow application using our tool. Finally, some concluding remarks are made and future work is outlined in Section 5.
2
Related Work
Java’s platform independent bytecode can be executed securely on many platforms, making Java an attractive basis for portable Grid computing. Java offers language elements to express thread based parallelism and synchronization. Therefore, its potential for developing parallel and distributed applications was noticed long before the Grid computing turn out to be relevant for computer scientists. Many projects tried to use the huge potential of the Internet by supplying Java-based systems for web-computing (e.g. Bayanihan[4], Javelin[5], JaWS[6]). Such systems are commonly based on volunteer computing and/or on a three-tier architecture with hosts, brokers and clients. Other systems are oriented towards cluster computing (e.g JavaParty[7], ProActive[8]) and offer high-level APIs for distributing Java objects over a computing resources of a cluster of workstations or a dedicated SMP cluster. The Grid community cannot ignore the advantages of using Java for Grid computing: portability, easy deployment of Java’s bytecode, component architecture provided through JavaBeans, a wide variety of class libraries that include additional functionality such as secure socket communication or complex message passing, etc. Moreover, Java Commodity Grid (CoG) Kit[9] allows access to the services provided by the Globus toolkit(http://www.globus.org).
3
JavaSymphony Preliminaries
JavaSymphony is a 100% Java library that enables the programmer to specify and control locality, parallelism, and load balancing at a high level of abstraction, without dealing with error-prone and low-level details (e.g. create and handle remote proxies for Java/RMI or socket communication). The developers of distributed application can use the JavaSymphony API to write distributed Java applications. A typical JavaSymphony application registers with the JavaSymphony Runtime System (JRS), allocates resources (machines where JRS is active), distributes code as Java objects among the resources, and invokes methods
20
A. Jugravu and T. Fahringer
Fig. 1. JavaSymphony on the Grid
of these objects. The objects may also communicate with each other through remote method invocation. Finally the application un-registers and is removed from the JRS’s list of active applications. Dynamic Virtual Distributed Architectures (called VAs) allow the programmer to define the structure and the characteristics of a heterogeneous network of computing resources (e.g. CPU type, speed, or machine configuration), and to control mapping, load balancing, migration of objects and code placement. JavaSymphony also offers possibilities to specify, control and query the properties of the computing resources. We call these properties constraints, which can be static (e.g. operating system name, available memory/disc space, java version, etc.) or dynamic (e.g. free memory, load, free disk space, network bandwidth and latency, etc.) JavaSymphony remote objects (JS objects) are used to distribute objects onto virtual architectures. Under JavaSymphony one can distribute any type of Java objects, by encapsulated them in JS Objects. The programmer is not forced to implement specific interfaces and to encode special methods. Thus any Java object can be used in parallel applications without adding a single line of code. The mapping of the JS objects can be explicit, on specific level-1 VAs (single resources), or controlled by constraints associated with the resources. JavaSymphony applications use the distributed objects by remotely invoking their methods. Other programming features offered by JavaSymphony include a variety of remote method invocation types (synchronous, asynchronous and one-sided); (un)lock mechanism for VAs and JS objects; high level API to access a variety of static or dynamic system parameters, e.g. machine name, user name, JVM version or CPU load, idle time, available memory; selective remote class-loading; automatic and user-controlled mapping of objects; conversion from Java conventional objects to JS objects for remote access; single-threaded versus multithreaded JS objects; object migration, automatic or user-controlled; distributed event mechanism; synchronization mechanisms and persistent objects. More details about the JavaSymphony programming constructs can be found in [1,3].
JavaSymphony, a Programming Model for the Grid
21
The JavaSymphony Runtime System (JRS) is implemented as an agent based system, with agents running on each computing resource to be used by JavaSymphony applications (see [1,2]). We intend to implement the JS agents as Grid services, running on various grid resources (see Figure 1). The JS applications correspond to Grid distributed applications. The resources are requested using VAs defined in the JS application. JS constraints provide support for managing, querying and monitoring the parameters of the resources. The JS objects play the role of Grid submitted Java jobs. In addition, the distributed components of an application may freely communicate each with other, a feature which is currently not supported or hard to implement for typical Grid applications. Other features like migration, events, synchronization may be extremely useful for collaborative Grid applications.
4
Grid Workflow Applications under JavaSymphony
We define a Grid Workflow application as a set of one or more linked activities, which collectively realize a common goal. Information (files, messages, parameters, etc.) is passed from one participant to another for action, according to a set of procedural rules and the whole process is using a Grid infrastructure. JavaSymphony programming paradigm is flexible enough to allow the implementation of a large range of distributed applications, including workflow applications. However, the developer usually has to manage the resources, build Java objects, and control the mapping of these objects onto resources. For better performance, the developer also must incorporate a scheduling strategy adapted to his particular applications. All these issues require a significant programming effort. Many distributed applications follow a well-defined pattern, and therefore many of the above-mentioned programming issues could be automated. We are particularly interested in automatic resource allocation and scheduling. In recent times, workflow applications became quite popular in Grid community and many research and industry groups proposed standards to model and develop workflow applications and built workflow definition languages or schedulers for workflow applications[10,11,12,13]. On the other hand the workflow applications may support automatic resource discovery, allocation and scheduling. Motivated by these aspects, we have considered to support the developing of workflow application in JavaSymphony. This support consists of: A graphical user interface for building the structure of a workflow, specify constraints associated with the resources or characteristics of the components (called activities) of the workflow. A specification language for describing the workflow and its components. We use an XML based language and we intend to keep it simple. A JavaSymphony workflow application will be automatically generated using the description of the workflow and the code for its activities. Library support for workflow applications consists of a set of classes used to standardize the workflows and their activities in JavaSymphony.
22
A. Jugravu and T. Fahringer
A specialized scheduler which automatically finds resources (as VAs), maps components onto resources and runs the distributed computation, according to the rules defined for the workflow. We have fully implemented the specification language and the GUI. Our GUI uses the same graphical engine as Teuta[14]. We are currently working on the library support and the scheduler for JavaSymphony workflow applications.
4.1
Workflow Model
Our tool is used to build the graphical representation of a workflow as a graph. We have followed the terminology and specifications proposed by the Workflow Management Coalition[15] and used several types of basic workflow elements: Activities. The activities perform the computational parts of a workflow. They are represented as vertices of the associated graph. Each activity will be associated with a Java class that extends the JSActivity abstract class provided by JavaSymphony library. Instances of the associated classes will be placed onto computing resources where they will perform specific computation. Dummy Activities. The dummy activities represent a special type of activities. They are supposed to perform evaluation of complex conditional expressions that may influence the scheduling of the workflow, but they require minimal computing power. They will not be placed onto distributed computing resources, but will run locally within the scheduler. Links. Between the vertices of the associated graph, there may be directed edges, which represent the dependency relation (dataflow or control flow dependency) between the activities. Sending data from one activity to another implies that there is also a control flow dependency between the two. Therefore we may consider that all links are associated with dataflow dependencies. Initial and Final States. Each workflow has an entry and an exit point, which we call initial state, respectively final state. These states are not associated with computation. They are also used to mark subworkflows of a workflow. Each subworkflow has a unique initial state and a unique final state. Conditional branches. The execution plan of a workflow is dynamically changed using conditional branches. In our model, a conditional branch has one entry (link from an activity to the conditional branch) and two or more exits. The successors of the conditional branch correspond to entry points of subworkflows. When the execution reaches the conditional branch, a single successor will be chosen and the rest of them will be omitted in the execution. Loops. For consistency reasons, the loops in JavaSymphony may be associated only with entire (sub)workflows units, with a single entry (initial state) and a single exit (final state) point. For a (sub)workflow which has a loop associated with it, the entire sequence of activities is executed repeatedly a fixed number of times (for-loops) or until an associated condition is satisfied (until-loops).
4.2
DES Encryption/Decryption Application
In the following, we show how we have used our tool to transform an existing JavaSymphony application into a workflow application. This application
JavaSymphony, a Programming Model for the Grid
23
Fig. 2. JavaSymphony DES decoding algorithm
implements DES encryption/decryption algorithm[16]. In previous work[1], we have studied the performance of this application in comparison with two other Java-based programming paradigms for concurrent and distributed applications: JavaParty[7] and ProActive[8]. DES encryption/decryption algorithm[16] uses a key of 56 bits, which is extended with another 8 parity bits. DES tries to detect the key that has been used to encrypt a message using DES, based on a “brute-force” approach (every possible key is tested). The assumption is that we know a string that must appear in the encrypted message. Figure 2(a) shows our original design of the DES decoding algorithm. The DesDecoder objects process a space of possible keys, which are provided by one or several KeyGenerator object(s). A DesDecoder acquires the keys from the KeyGenerator through a synchronous method invocation. The KeyGenerator keeps track of the keys that have already been generated. After the DesDecoders have decoded a message by using their asigned keys, a one-sided method invocation is used to transfer the decoded messages to a TextSearcher object, which validates it by searching the known string in the messages. The most important component of the application is the DESDecoder class. One DESDecoder plays an active role: it requests new data from a KeyGenerator as a DESJob, applies the decryption algorithm and sends (buffers of) processed data further to a TextSearcher, which (in)validates it.
4.3
DES Encryption/Decryption as a Workflow Application
The DES JavaSymphony application described above is not implemented as a workflow application. There are three types of functional components, which we used, but the data exchanged does not follow a “flow”, as for workflow applications. There is a bi-directional communication between KeyGenerator and (i.e. request and response), and respectively unidirectional be-
24
A. Jugravu and T. Fahringer
tween and (send data). However we can modify the functional components to build a workflow application. The activities of the workflow are associated with the three types of objects: KeyGenerator, DESDecoder and TextSearcher. There is workflow precedence between and DESDecoders, respectively between DESDecoders and TextSearchers (see Figure 2(b)). Dataflow precedence overlaps the workflow precedence: There is unidirectional communication from Key Generator to DESDecoders and from DESDecoders to TextSearchers. The implementation for the three classes has to be changed accordingly. The graphical representation of the workflow is shown in Figure 2(b) and has been built by using our tool. In our example, there are 2 KeyGenerator activities, 4 DESDecoder activities, and 3 TextSearcher activities represented as vertices. The arrows between vertices represent the links of the workflow (data and control flow). There is no need for conditional branches or dummy activities. The process is repetitive and therefore a loop is associated with the whole workflow. In addition, the developer has to implement the classes for the activities such that they implement a specific JavaSymphony interface for activities. Using the GUI, the developer associates the activities with these classes. He may also specify input parameters, resource constraints (for the VA generation), and activity characteristics relevant for the scheduling (e.g. estimated computation load, minimum/average/maximum execution time for the activity, priority etc.). For the data links between activities, one may specify link constraints (e.g. bandwidth or latency constraints) or communication characteristics (e.g. estimated communication load), which are relevant for the scheduling. The GUI produces a file, which describes the workflow (structure, constraints, characteristics of the workflow elements, etc.) in a XML-based workflow specification language . The scheduler will use the workflow description file to map activities of the workflow onto computing resources, to enact these activities and to control communication between them. The scheduler is currently under development.
5
Conclusions and Future Work
JavaSymphony is a system designed to simplify the development of parallel and distributed Java applications that use heterogeneous computing resources ranging from small-scale cluster computing to large scale Grid computing. In contrast with most existing work, JavaSymphony allows the programmer to explicitly control locality of data, parallelism, and load balancing based on dynamic virtual distributed architectures (VAs). These architectures impose a virtual hierarchy on a distributed system of physical computing nodes. JavaSymphony is implemented as a collection of Java classes and runs on any standard compliant Java virtual machine. No modifications to the Java language are made and no pre-processors or special compilers are required. In this paper we have presented a framework for developing Grid workflow applications in JavaSymphony. We consider that JavaSymphony offers a very
JavaSymphony, a Programming Model for the Grid
25
suitable programming paradigm for developing Java-based Grid applications. We plan to further investigate the applicability of JavaSymphony in the context of Grid computing and implement an automatic scheduler for JavaSymphony workflow applications.
References 1. Jugravu, A., Fahringer, T.: Javasymphony: A new programming paradigm to control and to synchronize locality,parallelism, and load balancing for parallel and distributed computing. to appear in Concurency and Computation, Practice and Experience (2003) 2. Jugravu, A., Fahringer, T.: On the implementation of JavaSymphony. In: HIPS 2003, Nice, France, IEEE (2003) 3. Fahringer, T., Jugravu, A., Martino, B.D., Venticinque, S., Moritsch, H.: On the Evaluation of JavaSymphony for Cluster Applications. In: IEEE International Conference on Cluster Computing (Cluster2002), Chicago USA (2002) 4. Sarmenta, L.F.G., Hirano, S., Ward, S.A.: Towards Bayanihan: Building an extensible framework for volunteer computing using Java. In ACM, ed.: ACM 1998 Workshop on Java for High-Performance Network Computing, New York, NY, USA, ACM Press (1998) 5. Alan, M.N.: Javelin 2.0: Java-based parallel computing on the internet (2001) 6. Lalis, S., Karipidis, A.: Jaws: An open market-based framework for distributed computing over the internet (2000) 7. Haumacher, B., Moschny, T., Reuter, J., Tichy, W.F.: Transparent distributed threads for java. In: 5th International Workshop on Java for Parallel and Distributed Computing ,Nice, France, April 22-26, IEEE Computer Society (2003) 8. Baude, F., Caromel, D., Morel, M.: From distributed objects to hierarchical grid components. In: International Symposium on Distributed Objects and Applications (DOA), Catania, Sicily, Italy, 3-7 November, Springer Verlag, Lecture Notes in Computer Science, LNCS (2003) 9. Laszewski, G., Foster, I., Gawor, J., Lane, P.: A java commodity grid kit. Concurrency and Computation: Practice and Experience 13 (2001) 10. Andrews, T., Curbera, F., Dholakia, H., Goland, Y., Klein, J., Leymann, F., Liu, K., Roller, D., Smith, D., Systems, S., Thatte, S., Trickovic, I., Weerawarana, S.: Business process execution language for web services (bpel4ws). Specification version 1.1, Microsoft, BEA, and IBM (2003) 11. Erwin, D.W., Snelling, D.F.: UNICORE: A Grid computing environment. Lecture Notes in Computer Science 2150 (2001) 12. The Condor Team: (Dagman (directed acyclic graph manager)) http://www.cs.wisc.edu/condor/dagman/. 13. Krishnan, S., Wagstrom, P., von Laszewski, G.: GSFL : A Workflow Framework for Grid Services. Technical Report, The Globus Project (2002) 14. Fahringer, T., Pllana, S., Testori, J.: Teuta: Tool Support for Performance Modeling of Distributed and Parallel Applications. In: International Conference on Computational Science. Tools for Program Development and Analysis in Computational Science., Krakow, Poland, Springer-Verlag (2004) 15. WfMC: Workflow Management Coalition: http://www.wfmc.org/ (2003) 16. Wiener, M.J.: Efficient DES key search, technical report TR-244, Carleton University. In: William Stallings, Practical Cryptography for Data Internetworks. IEEE Computer Society Press (1996)
Adaptation of Legacy Software to Grid Services 1,2 1 2
, Marian Bubak1,2, and
1
Institute of Computer Science, AGH, al. Mickiewicza 30, 30-059 Kraków, Poland Academic Computer Centre – CYFRONET, Nawojki 11, 30-950 Kraków, Poland {balis,bubak}@uci.agh.edu.pl,
[email protected]
Abstract. Adaptation of legacy software to grid services environment is gradually gaining in significance both in academic and commercial settings but presently no comprehensive framework addressing this area is available and the scope of research work covering this field is still unsatisfactory. The main contribution of this paper is the proposal of a versatile architecture designed to facilitate the process of transition to grid services platform. We provide thorough analysis of the presented solution and confront it with fundamental grid requirements. In addition, the results of performance evaluation of a prototype implementation are demonstrated. Keywords: Legacy software, grid services, design patterns
1 Introduction In this paper we intend to propose a versatile framework enabling for semiautomated migration from legacy software to grid services environment [1,8]. A detailed analysis of the presented solution can be found in [2] which contains rationale supporting our design decisions and justification for rejection of other approaches. Here, we outline the most recent stage of evolution of our concept and demonstrate the results of performance evaluation of its prototype implementation. The need for a framework enabling for cost-effictive adaptation of legacy software to grid services platform is a widely recognized issue. Nonetheless, it is still addressed inadequately as compared to its significance. We have summarized the related research, which originates from both academia and industry, in [2]. Recent experiences in this area were presented at the GGF9 Workshop [3]. Currently no comprehensive framework facilitating migration to grid services environment is available and, as discussed in [2], existing approaches [4,5] possess numerous limitations.
2
System Structure
In the proposed architecture, we can distinguish three main components: backend host, hosting environment and service client. As depicted in Fig. 1, they M. Bubak et al. (Eds.): ICCS 2004, LNCS 3038, pp. 26–33, 2004. © Springer-Verlag Berlin Heidelberg 2004
Adaptation of Legacy Software to Grid Services
27
Fig. 1. System architecture
are potentially located on separate machines. The presented diagram reflects the configuration for a single legacy system which is exposed as a grid service. Communication between components takes place by means of SOAP messages. Data is exchanged by remote method invocations performed on services deployed within the hosting environment.
2.1
Backend Host
Backend host represents the machine on which legacy software is installed and executed. In order to enhance performance and scalability as well as improve reliability and fault tolerance, we may decide to deploy several redundant copies of a single legacy application on different computing nodes, possibly in various geographic locations. For this reason, in the context of a particular service, we can end up having multiple backend hosts constituting dynamic pool of available processing resources. We propose the following approach to maintenance and utilization of such a conglomerate. Backend hosts do not fulfill the function of network servers. Instead, they are devised to act as clients. Legacy applications are not required to be directly accessible from the outside. We employ registration model. Backend hosts are expected to volunteer to participate in computations and offer their capabilities of serving client requests. Each backend host comprises two flavors of processes: master and slave ones. The master process is a permanent entity responsible for host registration and creation of slave processes. Whenever the load of a particular backend host in comparison with its resources allows it to serve a new client, the master process is obliged to report this fact by calling the registry service. Along with this invocation, the estimated processing capability (in the sense of a certain metric) and validity timestamp are provided. The call blocks until the given time
28
M. Bubak, and
expires or one of the pending clients is assigned. In the latter case, a new slave process is spawned in order to take over further processing. There is only one master process per host. Slave processes are transient – as clients come and go, the number of concurrently running slave processes changes respectively. These processes are in charge of direct collaboration with legacy software on behalf of the clients that they represent. This cooperation can assume various forms and range from local library usage to communication over proprietary protocols. The primary activity performed by each slave process is intercepting subsequent client invocations, translating them into legacy interface and delivering the obtained results. Slave processes communicate with the service container by means of blocking method invocations performed on the proxy instance.
2.2
Hosting Environment
The hosting environment contains a collection of grid services that jointly fulfill the role of shielding clients from unmediated interaction with backend hosts. For each legacy system, there are three permanent services deployed: registry, factory and proxy factory. Depending on the number of simultaneously served clients, we have varying number of transient services, two types of which exist: instance and proxy instance. Access to all services is authorized and restricted to subjects holding adequate identities. In case of internal services, such as registry, proxy factory and proxy instance, permission is granted on the basis of host certificates. For the remaining services, namely factory and instance, we employ user certificates. Clients are not eligible to use internal services. Moreover, both types of instances can be accessed exclusively by their owners. Registry is a service that controls the mapping between clients and backend hosts, which offered their participation in request processing. It is obliged to assign consecutively appearing clients to the chosen backend hosts. For the purpose of selection, registry maintains priority queue to which pending master processes are inserted. The ordering criterion is processing capability advertised during each registration. The remaining services form two pairs, each consisting of factory and the corresponding instance. We discriminate two types of factories and instances: ordinary and proxy ones. The former are designated for clients whereas the latter are auxiliary entities providing mediation facilities. Proxy entities are logically separated because they serve internal purposes and should be transparent to the clients.
3
System Operation
Let us now turn our attention to the scenarios that take place during typical client-service interaction. From the client’s perspective, the following sequence of actions normally is performed: (1) new service is created, (2) certain methods are invoked, (3) the service is destroyed. On the internal system side, each of the
Adaptation of Legacy Software to Grid Services
29
above-mentioned steps involves a number of activities. They are schematically presented in Fig. 2 as a time sequence diagram. The prerequisite for all depicted scenarios is an operative environment with permanent services up and running. Moreover, before any client interaction takes place, at least one master process should be registered in the context of the considered service. It is essential since otherwise no actual processing would be feasible.
Fig. 2. Scenarios: (1) service construction (2) method invocation (3) service destruction
All scenarios axe triggered by clients. Procedures accompanying service construction and destruction are executed by container’s callback methods connected with lifetime management. 3.1
Service Construction
The scenario of service construction encompasses several actions. In the first place, proxy factory is contacted and the corresponding proxy instance is created. Following this, registry service is invoked. As a result of this call, one of the registered master processes is selected and provided with the location of the newly deployed proxy instance. The chosen master process spawns a new slave process which in turn starts to wait for client requests using the created proxy instance.
M. Bubak, and
30
3.2
Method Invocation
After a successful initialization, three transient entities are created: instance, proxy instance and slave process. Since they cannot be shared, we can treat them as a private property of a particular client. Whenever a client invokes a method, its complete description, together with passed parameters, is forwarded to the proxy instance. The request is then further propagated to slave process. The call blocked on waiting for client action returns and slave process translates the obtained invocation to its legacy equivalent. Next, legacy processing is started. As soon as it is finished, the obtained results are supplied to the proxy instance via a separate asynchronous method invocation. This in turn causes that control is transferred back to service instance and after that to the client from which it originated. Effective scenario of method invocation is critical to the system performance due to the frequency with which it occurs. The communication between instance and proxy instance takes place within the borders of a local container so it should not pose a bottleneck. Apart from this, we have two internal remote invocations per client call.
3.3
Service Destruction
Grid services support explicit and soft state mode of destruction. The former takes place on client demand whereas the latter is executed automatically when instance lifetime expires. The scenario of service removal is relatively simple. The request of destruction is forwarded to proxy instance. Once it is delivered, it is intercepted by the slave process, which terminates its execution. In the next steps, proxy instance and instance are deleted by the container.
4
System Features
Having examined individual components and scenarios comprising the proposed architecture, we will now characterize it from a wider perspective and confront its properties with requirements that have to be satisfied in a grid environment.
4.1
Security
We can point out two major aspects concerning the security of our infrastructure. There is no need to introduce open incoming ports on backend hosts. It is possible to obtain the identity of machines with which we cooperate and verify that the processing is delegated only to trusted nodes. We owe both these advantages to the fact that backend hosts act as clients rather than servers. As we stated earlier, we perform authentication and authorization procedures. If needed, communication integrity and privacy can be ensured by means of digital signatures and encryption. In our solution security configuration
Adaptation of Legacy Software to Grid Services
31
can be thought of as two lists of identities. First for clients that are entitled to use our service, and second for hosts that are permitted to perform processing for our service. In consequence, maintenance of security policy should not involve excessive administrative effort.
4.2
Scalability
The combination of several factors enables to achieve high scalability of our architecture. Since actual processing is always delegated to backend hosts, computations can be heavily distributed across a large number of nodes. Furthermore, service instances residing in the container do not incur large resource consumption. Their activity is in fact reduced to message forwarding. Moreover, thanks to registration model we earn automatic load balancing. Backend hosts decide about client acceptance themselves and volunteer only when they can guarantee that processing can be finished within reasonable amount of time. This brings high responsiveness to unexpected changes in utilization. In addition, master processes advertise temporal capabilities of machines on which they are executed. This can be used for resource reservation, which is essential for the assurance of the quality of service.
4.3
Fault Tolerance
The proposed solution offers a high degree of resilience to component failures. The most important reason for this is the fact that processes are not bound to any specific endpoint. Being clients, they can arbitrarily change their location between subsequent method calls without any serious repercussions. Thus, process migration is supported. In case of legacy systems which maintain internal state or work in a transactional manner, process migration has to be disabled or automatic repetition of all preformed method invocations should be allowed. Immunity to sudden changes of configuration is ensured by the eager registration model. At any point in time, it is not necessary to poll backend hosts in order to determine operative nodes. We have up-to-date system image sustained continuously.
4.4
Portability
Unquestionably, an important advantage of our architecture is the fact that we make no assumptions as regards programming language or platform on which both backend host and hosting environment are based. Our solution is versatile enough to accommodate a variety of legacy systems and container implementations. Furthermore, legacy software can remain in the same location where it was initially installed. There is no necessity of moving programs between machines or changing their configuration.
32
5
M. Bubak, and
Performance Evaluation
In order to estimate the communication overhead introduced in the proposed framework, we developed a simple benchmark – echo grid service exposing a single method which repeated the string passed as its parameter. There were two functionally equivalent implementations of the above service. Measurements were performed on the client side and embraced solely method invocation scenario. No security mechanism was employed. In consequence, the results reflect the overhead introduced merely by our core architecture. The influence of different security modes on efficiency of Globus I/O library is quantified in [6]. We performed two types of tests: bandwidth- and latency-oriented. The former used large messages whereas the latter transmitted small amount of data. The experiment was carried out on a single-processor desktop machine running Linux operating system. It simultaneously played the role of the hosting environment, backend host and service client. As for software configuration, Globus Toolkit 3.0 [9] together with gSOAP 2.1 [10] were used. We performed time measurement for message payload being 1 and 105 bytes. Number of method calls ranged from 1 to 256 and 8192 for bandwidth and latency measurement, respectively. The obtained measurement results are presented in Fig. 3. In order to enhance clarity, logarithmic scale (base 2) is used. We observe a linear dependence between the number of method calls and the time needed for their execution. Thereby, the introduced overhead can be computed as a quotient of directional coefficients of linear approximations of individual functions.
Fig. 3. Results of performance evaluation
In case of transmitting small SOAP messages, the obtained ratio was 3.65 whereas for relatively large ones we got the proportion equal to 1.79. This phenomenon can be explained if we take into account that the impact of communication overhead diminishes along with the message enlargement.
Adaptation of Legacy Software to Grid Services
33
On the basis of the conducted experiments, we can draw a conclusion that in our architecture, in average case, we should expect approximately threefold decreased communication efficiency.
6
Concluding Remarks
Implementation of initial version of the presented framework took place while porting grid monitoring system, OCM-G [7], to grid services environment. This project served as a proof of the concept of the overall solution. Since then the architecture has undergone a number of refinements. Its current form is to a large extent stable. Our work is now focused on developing additional test cases in order to evaluate the proposed architecture under a variety of circumstances. The anticipated direction of project evolution is implementation of tools facilitating the application of our framework. This includes, among others, utilities allowing for automatic interface and code generation.
References 1. Foster, I., Kesselman, C., Nick, J., Tuecke, S.: The Physiology of the Grid. http://www.globus.org/research/papers/ogsa.pdf 2. Bubak, M., A Framework for Migration from Legacy Software to Grid Services. To be published in Proc. Third Cracow Grid Workshop, Cracow, Poland 2003. 3. Contributions to GGF9 Workshop Designing and Building Grid Services. http://www.gridforum.org 4. Huang, Y., Taylor, I., Walker, D., Davies, R.: Wrapping Legacy Codes for GridBased Applications. In Proc. International Workshop on Java for Parallel and Distributed Computing, Nice, France, 2003. 5. Kuebler, D., Eibach, W.: Adapting Legacy Applications as Web Services. http://www-106.ibm.com/developerworks/webservices/library/ws-legacy 6. Bubak, M., Szepieniec, T., Wismüller, R.: Two Aspects of Security Solution for Distributed Systems in the Grid on the Example of OCM-G. To be published in Proc. Third Cracow Grid Workshop, Cracow, Poland 2003. 7. Bubak M., Funika, W., Szczepieniec, T., Wismüller, R., Monitoring Grid Applications with Grid-enabled OMIS Monitor. In Proc. First European Across Grids Conference, Santiago de Compostela, Spain, February 2003. To appear. 8. Open Grid Services Infrastructure Specification. http://www.gridforum.org/ogsi-wg/ 9. Globus Project homepage: http://www.globus.org 10. gSOAP Project homepage: http://www.cs.fsu.edu/~engelen/soap.html
Grid Service Registry for Workflow Composition Framework Marian Bubak1,2, 1 2 3
2,3
, and Katarzyna Rycerz1,2
1
, Maciej Malawski1,2,
Institute of Computer Science, AGH, al. Mickiewicza 30, 30-059 Kraków, Poland Academic Computer Centre – CYFRONET, Nawojki 11, 30-950 Kraków, Poland Faculty of Sciences, Section of Computational Science, University of Amsterdam Kruislaan 403, 1098 SJ Amsterdam, The Netherlands {bubak,malawski,kzajac}@uci.agh.edu.pl
[email protected] ,
[email protected]
Abstract. The system presented in this paper supports the user in composing the flow of distributed application from existing Grid services. The flow composition system builds workflows on an abstract level with semantic and syntactic description of services available in a Grid services registry. This paper presents concepts of an overall system architecture and it focuses on one of the two main modules of the system – the distributed Grid service registry. Keywords: Grid workflow, workflow composition, distributed registry, ontologies, Grid programming
1
Motivation
The future Grid is often described as a geographically-distributed set of services deployed on different sites by some service providers. These Grid services, as described in the Open Grid Service Architecture (OGSA) specifications [7,12], should allow the user to do computations, access some resources, get information or use external scientific devices. Usually each of them will provide only a part of functionality required by the user, so using many of them, connected in a workflow, will be required quite often. It is one of the new approaches to programming Grid applications. Unfortunately, as the number of available services grows, the task of manual workflow composition becomes very difficult and time-consuming. A mature flow composition system is needed to support the user and thus make the task feasible. This kind of system would also help in fast Grid application development (prototyping) and in finding services appropriate for completing a partial solution prepared by the user. It would also allow for automatic, on-demand creation of workflows for specified tasks or rebuilding old workflows when they cannot be run on the Grid anymore due to frequent changes of the environment. Two approaches to mapping an abstract workflow defined in terms of application components onto a set of available Grid resources are presented in [5]. In the Web Services community, the most popular registry system M. Bubak et al. (Eds.): ICCS 2004, LNCS 3038, pp. 34–41, 2004. © Springer-Verlag Berlin Heidelberg 2004
Grid Service Registry for Workflow Composition Framework
35
is the Universal Description, Discovery and Integration standard [13]. The implementation of a distributed UDDI registry, within a full-fledged P2P environment, supported by sophisticated registry ontologies, can be found in METEOR-S [9, 4]. The core specification of the UDDI standard (already in version 3.0) also introduces a new, distributed registry architecture. A simpler, but still very flexible and efficient solution for sharing any kind of information stored in XML documents can be found in JXTA Search [14]. Another example of this approach is the myGrid project [10] where the improved UDDI system has been successfully introduced in a Grid OGSA environment. To the best of our knowledge, there is still no mature distributed system for semi-automatic workflow composition on a Grid. As a proof-of-concept and for feasibility studies we have developed a prototype of such a system – an Application Flow Composer (AFC) [2]. It is based on the Common Component Architecture (CCA) and builds flows comprised of CCA components. We perceive, however, that syntactic information about components (the types of their ports) is not sufficient for efficient workflow composition. The other disadvantage of the system is its centralization, leading to lack of scalability and fault tolerance. Therefore, we have decided to design a new, Grid-enabled distributed system. It is intended to be used to compose workflows from Grid services, utilizing their semantic description.
2
Overall Structure of the System
The new system consists of two main elements: a flow composer and a distributed registry (see Fig. 1). Both the flow composer and the registry are distributed and should run in a heterogeneous, geographically-spread Grid environment. They can communicate in a standard way (e.g. via SOAP) or, if the highest efficiency is required, via a dedicated, fast protocol. This distributed topology makes both subsystems more scalable and fault-tolerant. The roles of the flow composer and the registry can be explained with the following scenario. The user who wants to build a new Grid application consisting of Grid services, describes the initial conditions of the application workflow and sends them to flow composition unit. The flow composer divides this initial workflow document into smaller parts and tries to find appropriate solutions (in terms of Grid services) for each of them. To achieve this, it has to ask the registry for information about services that conform to a given semantic or syntactic description. After it finds all the necessary components, it combines results from all subtasks and builds the final workflow description that will be returned to the user. When multiple solutions can be applied, more than one final document is prepared. The user should choose the one that is the most appropriate. Sometimes the user’s help is required during the composition process. The system might ask the user questions in order to ease and speed up the decision-making process, especially regarding semantic matchmaking which is always difficult for an artificial entity. The flow composer architecture can be seen as a distributed set of agents, composing workflow on a user request. We use the well-known term agent for
36
M. Bubak et al.
Fig. 1. General view of the system architecture
describing the components of the flow composer, because each of them operates on behalf of the user, contains its own rules of quasi-autonomous decision making and uses resources (i.e. descriptions of Grid services). This agent-based approach has several advantages. It makes the solution scalable and efficient as the agents can spread on many resources and work together on one composition problem. It also imparts some fault-tolerance on the system as a failure of one agent shouldn’t stop the whole process. A more detailed description of the flow composer subsystem and the workflow composition process is given in [3]. The role of the distributed service registry in the entire framework is crucial. It is responsible for efficient delivery of data describing every available Grid service for the use of the flow composer. In this paper we describe our approach to building the registry together with requirements analysis and design.
3 3.1
Distributed Registry Requirements
The registry should enable publication and searching for information about components of a workflow. It should be as universal as possible in order to reduce the need for multiple registries within one Grid environment. However, as we are not able to make a registry capable of storing each kind of information, we will concentrate on Grid services and their descriptions, aiming at flexibility and
Grid Service Registry for Workflow Composition Framework
37
extensibility. The registry should meet the following requirements which stem from demands of Grid computing and the flow composition system: be distributed and scalable, be efficient, at least as far as searching for data is concerned (the speed of updating and inserting new data into the registry isn’t so crucial), allow for some redundancy of stored data (i.e. replication), thus lacking single points of failures, do not depend too much on the format of the information that can be stored, so new data formats can be introduced or the current one extended, be as fault-tolerant as possible, use technologies that are Grid-enabled, be simple to use.
3.2
Contents of the Registry
We want the registry to store information about Grid services. However, a simple syntactic description is not sufficient and should be extended so that every Grid service is described at least by: its unique identifier (within the whole Grid), the syntactic description of its ports and messages (e.g. WSDL), semantic information about the service itself and the ports, messages, tasks, data transformations, etc. it provides, the domain (or domains) it belongs to. This complete description of each Grid service will be called a Grid Service Information Document (GSID). We do not specify its format, however, we assume that it will be an XML document, which should guarantee portability, flexibility and extensibility. It will also allow for using many pre-existing technological solutions, such as parsers, XML databases, etc. The domain field enclosed in every GSID is used by the registry’s internal data distribution algorithm. All information in the registry is classified according to its domain, which can be, for example, a scientific domain (like biology, mathematics, etc). It can be a separate field, provided explicitly during service registration, or a function of the service’s semantic description. It plays a very important role and thus it should be selected carefully taking into account the following requirements: it should be itself a simple data structure, e.g. the name of an ontology, it must be a part of an uncomplicated structure (like a set of ontology trees) with not too many disjoint parts (e.g. trees), to enable efficient data distribution, the number of domains shouldn’t be too small, as it could limit the number of registry nodes, since these two quantities are strongly correlated. The user will be able get a list of all most general domains (ie. domains that have no parents) or a list of all direct subdomains of a specific domain from the registry. This will assure that at least for the “domain” field the ontologies
38
M. Bubak et al.
will be well known to users. The list of domains can change as users add more ontologies, however the uniqueness and global consistency of domain names in the whole registry is still guaranteed. The syntactical description of a Grid service is relatively simple. We can apply Grid/web service standards, like WSDL. The semantical description seems to be much more complicated. We have decided to use ontologies to express semantics, but the choice of notation is still to be made and many problems (e.g. whether to use shared or local ontologies) still have to be solved. Fortunately, many projects are exploring the areas of ontologies and semantic description of web/Grid services – these include OWL-S and the myGrid project [10,11].
3.3
Architecture of the Registry
The registry should be highly distributed and scalable. To achieve that, its architecture is a structure of equal and independent registry nodes with a given communication topology. By equal we mean that every node works in the same way and presents to the user the same interfaces. Therefore, the complicated structure of the registry is hidden behind the interfaces and all GSID documents can be accessed by sending requests to an arbitrary registry node regardless of their distribution within the whole registry. As long as the efficiency is not taken into account, it doesn’t matter for a user which node he or she will use to access the registry through one of its interfaces. The node that receives the user’s request is responsible for its proper redirection to other nodes of the registry when necessary. The algorithm of request redirection (routing) is under development. The problem is that no node can store complete information about data distribution within the whole registry as this solution wouldn’t be too scalable. On the other hand, remembering only the domains of the nearest neighbors may not be sufficient and broadcasting user’s requests throughout all the nodes should be strictly limited. Every registry node will be responsible for storing GSID documents related to some specific domains (see Fig. 2). The choice of nodes responsible for given domains can be done both manually, by a system administrator, and automatically, if that is allowed by the registry’s configuration. The main goal of such an approach is to store information very close to the places where the corresponding Grid services are deployed and/or most frequently used. It is reasonable to assume that every domain can be represented by at most one registry node as this solves problems of data coherency. However, data redundancy is required (see Sect. 3.1) so we have to introduce data replication between nodes, and, as efficiency remains essential, cache mechanisms should be added to the registry – this will require additional copying of data between many nodes. However, all data can be kept coherent and up-to-date in this kind of complicated structure and the concept of a single designated node for each domain, as well as other advanced techniques may be applied for that purpose. The number of registry nodes and the communication topology are dynamic so new nodes and interconnecting links can be added and removed without restarting. Of course, when
Grid Service Registry for Workflow Composition Framework
39
Fig. 2. Details of a single registry node
the number of nodes changes, some data has to be transferred and some time required to propagate all the required information throughout the whole registry.
3.4
Registry Interfaces
Each registry node will present the following interfaces to the outside world: a registration interface, a management interface and a lookup interface. The registration interface is responsible for publishing GSID documents and unregistering them when needed. The registration requester may be a user (e.g. a developer of a Grid service) or any other entity that can do it automatically (e.g. searching for services and then publishing some of them). The registration scenario can be the following: the user wants to register Grid service S in domain D (placed somewhere in one of the domain trees). If the domain doesn’t exist, a domain registration request has to be sent by a privileged entity. After that, service S can be registered by sending a registration request to any node of the registry. This node will take care of redirecting the request to the right place (the node responsible for domain D) at which service S will be registered. The lookup interface allows users to search for data in the registry. An essential step is the specification of the type of queries the registry should support. As data lookup should be very fast, we’d rather not put any complicated ontological reasoning machine inside the registry. On the other hand, we cannot confine users to using only these queries that are related to syntactic information (this would be highly insufficient e.g. for our flow composer). Thus, the following types of queries should be supported by the registry:
40
M. Bubak et al.
search by ID, search by syntactic information, search by semantic service description but using only names of ontologies and their attributes, not ontological reasoning. In the last case, the entity that is asking a question is limited only to queries like: “find all services that have ports which are described by one of the following ontologies: The registry does not care about ontological relations; it only compares names of ontologies (strings). However, these relations might be introduced here by the entity asking the question, by properly preparing the list of ontology names that is put in the query (e.g. and may be subclasses of This approach should be efficient and flexible. In order to make the migration of clients closer to data possible (e.g. agents of the flow composer) the registry will, in response to a query, return information on where exactly (i.e. on which node) the requested GSID document has been found. It will enable selecting the node which stores the data the user is looking for and asking next questions directly there, thus speeding up the lookup process.
4 Implementation Choices It’s now too early to make detailed implementation choices; we thus prefer to point out several requirements. First of all, as we would like the system to be portable, the use of a highly portable programming language (e.g. Java or C#) is desirable. Secondly, as the system has to be distributed, scalable and, at the same time, efficient, a non-hierarchical peer-to-peer paradigm with a lightweight underlying platform and fast communication protocols should be used. This will also allow for automatic deployment of system components in containers on nodes. For the first prototype of the system we are going to use Globus Toolkit 3.0 [8] as a hosting environment. For ontological reasoning we might use the Jena2 framework [15]. The registry should be conformable to a well-known standard to make it more universal and portable. This can be, for example, the third version of the UDDI specification that already supports distributed registries and data replication [13]. As the registry is going to be itself a Grid application, it seems obvious that it has to use a platform that is Grid-enabled. This could be one of the existing peer-to-peer environments or Grid middleware packages. We are considering using the JXTA Search system as a base and extending it with the required functionality. For an internal registry document database we investigate the possibility of using XML-dedicated database management systems, like Apache Xindice [1]
5
Conclusion and Future Works
This paper presents the design of a workflow composition system, with emphasis on the registry component (service). The general concept of a distributed registry is proposed basing on nodes specialized according to data domains, with
Grid Service Registry for Workflow Composition Framework
41
mechanisms of data replication and caching. The main interfaces of the registry are designed to meet the requirements of the flow composition system. While the main functionality of the registry system is defined, there are still many issues that need to be solved, e.g. the choice of data replication mechanisms, query routing among registry nodes and implementation technologies. Our current work is focused on these issues and on implementing the proof-of-concept prototype. The following algorithms and related protocols still have to be developed: request redirection algorithm, data replication algorithm, request and response caching, fault tolerance, backup servers. Acknowledgements. This work was partly funded by the European Commission, Project IST-2001-32243, CrossGrid, Project IST-2001-34808, GRIDSTART and the Polish State Committee for Scientific Research, SPUB-M 112/E356/SPB/5.PR UE/DZ 224/2002-2004. We are grateful to Piotr Nowakowski for his comments.
References 1. Apache Xindice, The Apache XML Project, http://xml.apache.org/xindice 2. Bubak, M., Górka, K., Malawski, M., Component-based System for Grid Application Workflow Composition, in: Dongarra, J., et al. (Eds.): 10th European PVM/MPI Users’ Group Meeting, Venice, Italy, September 29 October 2, 2003, Proceedings. LNCS 2840, Springer 2003, pp. 611-618 3. Bubak, M., Malawski, M., Rycerz, K.: Design of Distributed Grid Workflow Composition System. Cracow Grid Workshop 2003, November 2003, CYFRONET-AGH, Cracow http://www.cyfronet.krakow.pl/cgw03 4. Cardoso, J. and Sheth, A.: Semantic e-Workflow Composition. Journal of Intelligent Information Systems (JIIS), Vol. 12, 191-225, 2003 5. Deelman, E., et al.: Mapping Abstract Complex Workflows onto Grid Environment. Journal of Grid Computing 1, 25-39, 2003 6. Expert Group Report: Next Generation Grid(s), European Grid Research 20052010, June 2003 7. Foster, I., et al.: The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. OGSA WG, Global Grid Forum, June 2002 8. Globus Toolkit 3.0, http://www.globus.org/ogsa 9. METEOR-S Project: http://lsdis.cs.uga.edu/proj/meteor/SWP.htm 10. myGrid Project, http://mygrid.man.ac.uk/ 11. OWL-S http://www.daml.Org/services/owl-s/1.0/ 12. Tuecke, S., et al.: Open Grid Services Infrastructure (OGSI) version 1.0, OGSI WG, Global Grid Forum, June 2003 13. UDDI 3.0 http://www.oasis-open.org/committees/uddi-spec/doc/tcspecs.htm 14. JXTA Search web page, http://search.jxta.org/ 15. Jena – A Semantic Web Framework for Java, http://jena.sourceforge.net/
A-GWL: Abstract Grid Workflow Language* Thomas Fahringer1, Sabri Pllana2, and Alex Villazon1 1
Institute for Computer Science, University of Innsbruck Technikerstraße 25/7, 6020 Innsbruck, Austria {Thomas.Fahringer,Alex.Villazon}@uibk.ac.at 2 Institute for Software Science, University of Vienna Liechtensteinstraße 22, 1090 Vienna, Austria
[email protected]
Abstract. Grid workflow applications are emerging as one of the most interesting application classes for the Grid. In this paper we present AGWL, a novel Grid workflow language to describe the workflow of Grid applications at a high level of abstraction. A-GWL has been designed to allow the user to concentrate on describing scientific Grid applications. The user is shielded from details of the underlying Grid infrastructure. AGWL is XML-based which defines a graph of activities that refers to computational tasks or user interactions. Activities are connected by controland data-flow links. We have defined A-GWL to support the user in orchestrating Grid workflow applications through a rich set of constructs including sequence of activities, sub-activities, control-flow mechanisms (sequential flow, exclusive choice, and sequential loops), data-flow mechanisms (input/output ports), and data repositories. Moreover, our work differs from most existing Grid workflow languages by advanced workflow constructs such as parallel execution of activities with pre- and postconditions, parallel loops, event-based synchronization mechanisms, and property-based selection of activities. In addition, the user can specify high-level constraints and properties for activities and data-flow links.
1
Introduction
In the past years extensive experience has been gained with single site applications and parameter studies for the Grid. For some time, Grid workflow applications are emerging as an important new alternative to develop truly distributed applications for the Grid. Workflow Grid applications can be seen as a collection of activities (mostly computational tasks) that are processed in some order. Usually both control- and data-flow relationships are shown within a workflow. Although workflow applications have been extensively studied in areas such as business process modeling [12,5] and web services (BPEL4WS [2], XLANG [10], WSFL [7], SWFL [4]), this programming model is relatively new in the Grid computing area. * The work described in this paper is supported in part by the Austrian Science Fund as part of Aurora Project under contract SFBF1104. M. Bubak et al. (Eds.): ICCS 2004, LNCS 3038, pp. 42–49, 2004. © Springer-Verlag Berlin Heidelberg 2004
A-GWL: Abstract Grid Workflow Language
43
Low-level XML-based workflow languages, like Grid Service Flow Language (GSFL) [6] and Grid Workflow [3], have been proposed to describe Grid workflow applications. However, these languages are missing some important control flow constructs such as branches, loops, split and join. In the GridPhyN Project [1], Grid workflow applications are constructed by using partial/full abstract descriptions of “components”, which are executable programs that can be located on several resources. Their abstract workflow is limited to acyclic graphs. Moreover, a reduced data-flow model (no customization is allowed) is supported, and there is no advanced parallel execution of components. In the GridLab Triana Project [11], workflows are experiment-based: Each unit of work is executed for a specific experiment. A workflow (task graph) defines the order in which experiments are executed. Simple control-flow constructs can be used to define parallel processing, conditional execution (if, switch) and iterations (simple sequential loops and while). In this paper we describe the Abstract Grid Workflow Language (A-GWL) which allows the user to compose scientific workflow applications in an intuitive way. A-GWL is an XML-based language for describing Grid workflow applications at a high level of abstraction without dealing with implementation details. A-GWL does not consider the implementation of activities, how input data is delivered to activities, how activities are invoked or terminated, etc. A-GWL has been carefully crafted to include the most essential workflow constructs including activities, sequence of activities, sub-activities, control-flow mechanisms, data-flow mechanisms, and data repositories. Moreover, we introduce advanced workflow constructs such as parallel activities, parallel loops with pre- and postconditions, synchronization mechanism, and event based selection of activities. We support advanced data-flow constructs such as direct communication and broadcast communication. In addition, the user can specify high-level constraints on activities and on data-flow in order to support the underlying workflow enactment machine to optimize the execution of workflow applications. The paper is organized as follows. Section 2 depicts the workflow application development process, from the abstract and concrete level to the execution of the workflow application (composition, reification and execution). Section 3 introduces the basic concepts of A-GWL as well as advanced constructs for controland data-flow. Finally, Section 4 concludes the paper.
2
Overview
In this section we give an overview of our Grid workflow application development process from abstract representation, to the actual execution on the Grid. Figure 1.a depicts the complete process of developing a Grid workflow application. Figure 1.b shows the flow of three fundamental activities Composition, Reification and Execution. The dashed lines indicate the iterative process of workflow application development. Composition. The user composes the Grid workflow by using the Unified Modeling Language (UML) [8]. Alternatively, a High-level Textual Representa-
44
T. Fahringer, S. Pllana, and A. Villazon
Fig. 1. The development of Grid workflow applications. Acronyms: UML - Unified Modeling Language, HTR - High-level Textual Representation, A-GWL - Abstract Grid Workflow Language, C-GWL - Concrete Grid Workflow Language.
tion (HTR) may be used for the workflow composition. Our tool Teuta [9] supports the UML based workflow composition, and the automatic conversion to Abstract Grid Workflow Language (A-GWL). A-GWL is an XML based language for describing the Grid workflow at a high level of abstraction. At this level activities correspond mostly to computational entities and the specification of its input and output data. There is no notion of how input data is actually delivered to activities, or how activities are implemented, invoked and terminated. A-GWL contains all the information specified by the user during the workflow composition. Reification. The software infrastructure transforms A-GWL to the Concrete Grid Workflow Language (C-GWL). C-GWL contains the information specified by the user and the additional information provided by the software infrastructure (i.e. the actual mapping to Grid resources), which is needed for the execution of the workflow. It describes the realization of A-GWL by specifying how activities are actually implemented (e.g. Grid services), how they are deployed, invoked, and terminated. C-GWL also describes how data is transferred and in what form. C-GWL is an XML based language as well. Currently, we are in the process of the development of specification for C-GWL. Execution. C-GWL is interpreted by the underlying workflow enactment machine to construct and execute the full Grid workflow application.
3
A-GWL Constructs
In A-GWL, an activity is a generic unit of work. At this level, it is not seen how the activity is implemented at the concrete level. An activity may be mapped to Grid services, software components or web services under C-GWL. A workflow instance is the mapping of an A-GWL workflow to a C-GWL workflow that is actually executed on the Grid. Different workflow instances can run concurrently. The user can specify constraints that are used to tune the execution of the
A-GWL: Abstract Grid Workflow Language
45
workflow application. An activity can be a basic computation, a sequence of activities, or a composed sub-activity. The composition of the application is done by specifying both control-flow and data-flow between activities. A-GWL supports basic control-flow (sequential flow, exclusive choice and sequential loops) and advanced control-flow constructs such as parallel execution of activities, parallel loops with pre- and postsynchronizations and selection of activities. Basic data-flow is specified by connecting input and output ports between activities. The user can associate constraints with data-flow, which will be mapped, e.g., to concrete mechanisms that utilise secure communication or advanced QoS for data-transfer. In addition to basic data-flow between activities, A-GWL supports advanced data-flow between activities and repositories. In the following, we describe the most essential A-GWL elements in more detail.
3.1
Basic Elements
ACTIVITY: An activity in A-GWL is presented as a black-box with input/output ports, constraints, and properties. Input and output ports are used to specify the data-flow. Control-flow is made through explicit links among activities and by using different control-flow constructs (e.g. sequences, loops, etc). The user specifies data-flow by connecting input and output ports among activities which may not necessarily be directly connected with control flow links. Additional information about activities can be provided through constraints and properties. Constraints provide additional information that should be honored by the underlying workflow enactment engine when executing the Grid workflow application. Examples for constraints are as follows: execute activity on Grid machines running under a specific operating system, with a minimum amount of free dynamic memory, with more than some pre-defined idle time value, deployment requirements, etc. Properties describe information that can be useful for the workflow enactment engine for instance to schedule applications. Performance information (estimated execution times or floating point operations) is frequently indicated via properties. The XML representation1 for the ACTIVITY construct is given as follows,
Every activity, input, output, control-in and control-out have a unique name in a workflow application. Input and output ports can be used to specify dataflow between activities and/or repositories (see Section 3.4 and 3.5). 1
We use the notation convention from [2] for the informal syntax of XML grammar.
46
T. Fahringer, S. Pllana, and A. Villazon
A-GWL supports the notion of hierarchical decomposition of activities. An activity containing other activities (sub-workflow), is also an activity. In that case, all the input ports of the incoming activities of the sub-workflow are mapped to the input ports of the composed activity, and the output ports of all the outgoing activities are mapped to the output ports of the composed activity. Analogously (re)connections are handled for the control-flow.
3.2
Basic Control-Flow
A-GWL supports basic control-flow among activities as in conventional programming languages. The control-flow constructs are: the standard sequential flow (SEQUENCE), exclusive choice (SWITCH, IF-THEN-ELSE), and sequential loops (FOR, WHILE and DO-UNTIL). A-GWL can be used to specify multiple exits from loops. The BREAK construct can be used to exit the execution of a loop construct. We also support an EXIT construct to terminate the execution of the entire workflow instance.
3.3
Advanced Control-Flow
In addition to basic control-flow constructs that are commonly found in workflow languages, A-GWL supports advanced control-flow elements that are highly useful for scientific Grid workflow applications. These constructs provide the user with enough abstraction to compose advanced and complex Grid workflow application and specify concurrency in a very natural way (parallel execution of activities, parallel loops). PARALLEL: The PARALLEL construct is used to execute activities concurrently. The XML representation of the PARALLEL construct is as follows,
Before executing the activities specified in
, the preCondition is evaluated for all the activities. Only those that evaluate to true, are executed concurrently. If no preCondition is specified, all the activities are executed in parallel. The user can also specify a synchronizing post-condition (syncCondition) in order to wait for specific activities at the end of the PARALLEL construct, and then continue the control-flow, e.g. this feature can be used to select the fastest activity. Other examples of post-conditions include “wait for all activities to finish”, “wait for one”, and so on. If no syncCondition is specified, the PARALLEL construct will wait for all activities to be finished. By default, the same input is passed to each parallel activity. However, different input sources can also be specified, e.g. from other activities or from repositories (see Section 3.5 for advanced data-flow). Finally, the optional <default> activity inside the PARALLEL construct is used to specify an activity that is executed if all the pre-conditions of all activities of a parallel construct evaluate to false., and the input of B as tag (see Section 3.1). For instance, an activity A that wants to store its output (named oA) in a repository R, must simply define the following output: [email protected] [email protected] [email protected] 2[email protected] [email protected] [email protected] [email protected] [email protected] [email protected] , http://www.lkn.ei.tum.de[email protected] [email protected] , {fabien.chanussot,pascale.primet}@ens-lyon.fr 2[email protected] 3[email protected] , [email protected] , [email protected] 2[email protected] [email protected] http://hpc.cs.tsinghua.edu.cn[email protected] , [email protected] 2[email protected] 3[email protected] [email protected] [email protected] [email protected] [email protected] 3[email protected] [email protected] [email protected] [email protected] , http://homepages.inf.ed.ac.uk/stg/research/ENHANCE/[email protected] [email protected] [email protected] [email protected] 2[email protected] http://www.abo.fi/~xzhou[email protected] [email protected] [email protected] [email protected] [email protected] [email protected] [email protected] [email protected] 2> 2002, “Model Engineering, Concepts and Tools”, LNCS 2460, Dresden, Germany. Springer-Verlag, October 2002. 7. S. Pllana and T. Fahringer. UML Based Modeling of Performance Oriented Parallel and Distributed Applications. In Proceedings of the 2002 Winter Simulation Conference, San Diego, California, USA, December 2002. IEEE. 8. S. Pllana, T. Fahringer, J. Testori, S. Benkner, and I. Brandic. Towards an UML Based Graphical Representation of Grid Workflow Applications. In The 2nd European Across Grids Conference, Nicosia, Cyprus, January 2004. Springer-Verlag. 9. K. Schwarz, P. Blaha, and G. Madsen. Electronic structure calculations of solids using the WIEN2k package for material sciences. Computer Physics Communications, 147:71–76, 2002. 10. Herb Schwetman. Model-based systems analysis using CSIM18. In Winter Simulation Conference, pages 309–314. IEEE Computer Society Press, 1998. 11. Hong-Linh Truong and Thomas Fahringer. SCALEA: A Performance Analysis Tool for Distributed and Parallel Program. In 8th International Europar Conference(EuroPar 2002), Lecture Notes in Computer Science, Paderborn, Germany, August 2002. Springer-Verlag.[email protected] [email protected] [email protected] [email protected] [email protected] , [email protected] , [email protected] [email protected] [email protected] , [email protected] [email protected] element in the XML manifest and each associated file as a element within its resource. From the implementation point of view, a package is defined by: a specially named XML file, the top-level manifest; all XML control documents it refers along with the actual physical files, all grouped together in a logical directory. The top-level manifest describes the package itself. It contains the following sections: meta-data section - an XML element describing the whole manifest; organizations section - an XML element describing several organizations of the content within a manifest; resources section - an XML element referencing all of the actual resources and media elements needed for a manifest, including meta-data describing the resources, and references to any external files; (sub)manifest - one or more optional, logically nested manifests; Physical Files - these are the actual media elements, text files, graphics, and other resources as described by the manifest(s). The physical resources may be organized in sub-directories. Characterizing an instructional content is up to the content developer. If a package is meaningful only as a whole, then it should be described by the top-level manifest only. If a package contains elements that can be used on their own, each one of these elements should be described by a nested (sub)manifest in the top-level one. Thus, disaggregation of content is allowed. If we consider a package at the curriculum level, the top-level manifest has to comprise all course-level manifests as well as any instructional object of each course. The benefit of complying to the Content Package standard stands in the interplatform operability of the content as well as in its potential reusability.[email protected] [email protected] [email protected] [email protected] 2[email protected] [email protected] [email protected] [email protected] [email protected] , {Jean-Charles.Creput,Vincent.Hilaire,Abder.Koukam}@utbm.fr[email protected] [email protected] [email protected] [email protected] 3[email protected] [email protected] [email protected] [email protected] 3[email protected] [email protected] 3[email protected] 4[email protected] [email protected] University of Texas at Austin, Austin TX, USA, [email protected] 4 Duke University, Durham NC, USA, [email protected] [email protected] [email protected] 3[email protected] [email protected] [email protected] [email protected] 2[email protected] [email protected] [email protected] http://www.cs.rutgers.edu/~dnm[email protected] [email protected] [email protected] 5[email protected] [email protected] [email protected] [email protected] [email protected] [email protected] http://www.cse.ogi.edu/CHCC[email protected] [email protected] indicates the name of the animation to play, among those that are loaded in memory upon start-up by the rendering application. We refer to these animations as elementary or primitive animations. The tag is used to specify additional animation-related information while <startTime> provides timing information for the start of the animation. The optional item <stopTime> is not being used because we did not want to explicitly set the duration of the animation. In addition to elementary animations, more complex non-verbal behaviors can be created, assigned a name, and stored by the response generator. To create a new animation, its behavior must be defined in terms of existing animations. For example, assuming the existence of an animation called PUFF, a new composite animation GIVE_UP_FRUSTRATED can be created using PUFF and DONT_KNOW. Because the rendering engine recognizes only elementary animations, to play the new animation, the response generator has to create as many different XML representation strings as the number of primitive animations used in the description of the new one, i.e. two for GIVE_UP_FRUSTRATED. Sequentiality, parallelism and partial overlapping of existing animations to create the new animation can be tuned by setting appropriate values for the temporal items in the XML representation. So, GIVE_UP_FRUSTRATED can occur either as sequence of DONT_KNOW and PUFF, or vice versa, or by having these two running simultaneously, etc. In the our first prototype, we use approximately 300 spoken utterance templates, many of which are no-variable stories to be told by HCA, and 100 different nonverbal behavior primitives that we identified after analyzing a 4-hour video recording of a human actor performing as HCA in a children theater in the city of Odense, Denmark.[email protected] , {gkatsion,kman}@singular.gr[email protected] , {elenaz,sloot}@science.uva.nl[email protected] [email protected] 3[email protected] , [email protected] [email protected] , http://vlab.psnc.pl/[email protected] 2 TecMinho, Universidade do Minho, Campus de Azurem, 4800-058 Guimaraes, Portugal[email protected] [email protected] [email protected] ).[email protected] [email protected] [email protected] [email protected] [email protected] ,[email protected] 3[email protected] [email protected] ,[email protected]
[email protected] , 2[email protected] [email protected] ,[email protected] [email protected] 2 Institute of Computational Mathematics and Mathematical Geophysics Russian Academy of Sciences (Siberian Branch), [email protected] [email protected] [email protected] [email protected] [email protected] [email protected] ,{syhan,kckim}@konkuk.ac.kr, [email protected] , [email protected] , Jun 2003. 2. Thierry Ernst, Network Mobility Support Goals and Requirements, Internet Draft, , May 2003. 3. Thierry Earnst, Hong-You Lach, Network Mobility Support Terminology, Internet Draft, < draft-ietf-nemo-terminology-00.txt>, May 2003. 4. Vijay Devarapalli, Ryuji Wakikawa, NEMO Basic Support Protocol, Internet Draft, < draft-ietf-nemo-basic-support-01.txt>, Sep, 2003. 5. Kyeong-Jin Lee, J H Jeong, Route Optimization for Mobile Nodes in Mobile Network based on Prefix Delegation, Internet Draft, , Jun 2003. 6. W. Fenne, Internet Group Management Protocol, version 2, RFC2236. 7. V. Chikarmane et al, Multicast Support for Mobile Hosts Using Mobile IP: Design Issues and Proposed Architecture, ACM/Baltzer Mobile Networks and Applications, vol 3, no 4, pp 365-379, January 1999. 8. Hee-Sook Shin, Young-Joo Suh, and Dong-Hee Kwon, Multicast Routing Protocol by Multicast Agent in Mobile Networks, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, pp 271-278. 9. Kuang-Hwei Chi, Chien-Chao Tseng and Ting-Lu Huang, A Framework for Mobile Multicast using Dynamic Multicast Route, The computer journal, vol 42, no 6, 1999. 10. Thubert, P., and Molteni, M., Taxonomy of Route Optimization Models in the NEMO Context, Internet Draft: draft-thubert-nemo-ro-taxonomy-00, Oct 2002 1.[email protected] [email protected] [email protected] [email protected] 2 Indian Institute of Technology, Kharagpur, West Bengal 721302, India. School of Electronics and Information, Chonbuk National University, Jeonju, Korea. [email protected] [email protected] [email protected] fixes the number of input events (six, in the above BNF, each one yielding a next-state/output pair, i.e., ). In contrast to the classic GA, where genes are simple bit-sequences and crossover may be performed at any point, GPK only permits crossover by swapping sub-trees (of a couple) starting with the same non-terminal symbols (i.e., symbols between corner brackets). Moreover, the mutation operation is implemented as a crossover operation between the selected individual and a temporary random-derived tree.[email protected] 
