We present a concise, generic, and configurable partitioning approach for decomposable, modular, and multiscale (or hierarchical) constructive models. A generic model partitioning (GMP) algorithm decomposes a given multiscale model to a set of partition blocks based on a cost modeling and analysis method in polynomial time. It minimizes model decompositions and constructs monotonically improved partitioning outcomes during the partitioning process. The cost modeling and analysis method enables translating subjective, domain-specific, and heterogeneous resource information to objective, domain-independent, and homogeneous cost information. By translating models to a homogeneous cost space and describing partitioning logics over the space, the proposed algorithm utilizes domain-specific knowledge to produce the best partitioning results without any modification of its programming logics. As a consequence of its clean separation between domain-specific partitioning requirements and goals, and generic partitioning logic, the proposed algorithm can be applied to a variety of partitioning problems in large-scale systems biology research utilizing distributed and parallel simulation. It is expected that the algorithm improves overall performance and efficiency of in silico experimentation of complex multiscale biological system models.
Kitano, H.2002. Computational systems biology . Nature420: 206— 210 .
2.
Idekeer, T. , T. Galitski , and L. Hood.2001. A new approach to decoding life: Systems biology. Annual Review of Genomics andHuman Genetics2: 343—372 .
3.
Hood, L.2003. Systems biology: Integrating technology, biology, and computation. Mechanisms ofAgeing and Development124(1): 9— 16 .
4.
Park, S.2003. Cost-based partitioning for distributed simulation of hierarchical, modular DEVS models. PhD Dissertation. Department of Electrical and Computer Engineering, University of Arizona .
5.
Park, S. , C.A. Hunt , and G.E.P. Ropella.2005. Pisl: A large-scale in silico experimentation framework for agent-directed physiological models . In Proceedings of the 2005 Agent-Directed Simulation Symposium, Spring Simulation Conference, San Diego, CA.
6.
Zeigler, B.P. , H. Praehofer , and T.G. Kim.2000. Theory of Modeling and Simulation, 2nd edn. San Diego, CA: Academic Press .
7.
Vangheluwe, H.L.2000. DEVS as a common denominator for multi-formalism hybrid systems modeling . In Proceedings of the 2000 IEEE International Symposium on Computer-Aided Control System Design, Anchorage, AK.
8.
Zeigler, B.P.2003. DEVS today: Recent advances in discrete event-based information technology . In Proceedings of the 11th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer Telecommunications Systems (MASCOTS 2003), Orlando, FL , pp. 141—161.
9.
Djafarzadeh, R. , G. Waineer , and T. Mussivand.2005. DEVS modeling and simulation of the cellular metabolism by mitochondria . In Proceedings of the 2005 DEVS Integrative M&S Symposium, Spring Simulation Conference , San Diego, CA, pp. 55—62.
10.
Hu, X. , and D.H. Edwards.2005. Behaviorsim: A simulation environment to study animal behavioral choice mechanisms . in Proceedings of the 2005 DEVS Integrative M&S Symposium, Spring Simulation Conference, San Diego, CA.
11.
Biermann, S. , A.M. Uhrmacher , and H. Schumann.2004. Supporting multi-level models in systems biology by visual methods . In Proceedings of the 18th European Simulation Multiconference, Magdeburg, Germany.
12.
Uhrmacher, A.M. , D. Degenring , and B.P. Zeigler.2005. Discrete event multi-level models for systems biology . Lecture Notes in Computer Science Vol. 3380. Berlin: Springer , pp. 66—89 .
13.
Seo, C. , S Park , B. Kim , S. Cheon , and B.P. Zeigler.2004. Implementation of distributed high-performance devs simulation framework in the grid computing environment . In Proceedings of the 2004 Advanced Simulation Technologies Conference (ASTC '04) — High Performance Computing Symposium2004 (HPCS 2004), Arlington, VA.
14.
Cheon, S. , C. Seo , S. Park , and B.P. Zeigler.2004. Design and implementation of distributed DEVS simulation in a peer-to-peer network system . In P roceedings of the 2004 Advanced Simulation Technologies Conference (ACTS '04) — Design, Analysis, and Simulation of Distributed Systems Symposium2004 (DASD 2004), Arlington, VA.
15.
Pothen, A.1996. Graph partitioning algorithms with applications to scientific computing. In Parallel Numerical Algorithms, D. E. Keyes , A. Sameh , and V. Venkatakrishnan , eds. Dordrecht: Kluwer , pp. 323—368.
16.
Fjällström, P.-O.1998. Algorithms for graph partitioning: A survey. Linkköping Electronic Articles in Computer andInformation Science3(10).
17.
Alpert, C.J. , and A.B. Kahng.1995. Recent directions in netlist partitioning: A survey . SIAM Journal on Scientific Computing16(1—2): 452—469 .
18.
Schloegel, K. , G. Karypis , and V. Kumar.2004. Graph partitioning for high performance scientific simulations . Computing Reviews45(2).
19.
Karypis, G. , and V. Kumar.1998. A fast and high quality multilevel scheme for partitioning irregular graphs . SIAM Journal on Scientific Computing20: 359—92 .
20.
Barnard, S.T. , and H.D. Simon.1994. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems . Concurrency: Practice and Experience6: 101—17 .
21.
Saab, Y.G.2004. An effective multilevel algorithms for bisecting graphs and hypergraphs . IEEE Transactions on Computers53(6): 641—52 .
22.
Möller, M.O. , and R. Alur.2001. Heuristics for hierarchical partitioning with application to model checking . In Proceedings of the 11th IFIP WG 10.5 Advanced Research Working Conference on Correct Hardware Design and Verification Methods, Livingston, Scotland, pp. 71—85.
23.
Walshaw, C.2004. Multilevel refinement for combinatorial optimisation problems . Annals of Operations Research131(1—4): 325— 72 .
24.
Kim, K. , T. Kim , and K. Park.1998. Hierarchical partitioning algorithm for optimistic distributed simulation of DEVS models. Journal ofSystems Architecture44: 433—55 .
25.
Zhang, G. , and B.P. Zeigler.1990. Mapping hierarchical discrete models to multiprocessor system: Concept, algorithm, and simulation . Journal of Parallel and Distributed Computing9: 271—80 .
26.
Kernighan, B. , and S. Lin.1970. An efficient heuristic procedure for partitioning graphs. The BellTechnical Journal49: 291—307 .
27.
Dutt, S.1993. New faster Kernighan—Lin-type graph-partitioning algorithms . In Proceedings of the 1993 IEEE/ACM International Conference on Computer-aided Design, Santa Clara, CA, pp. 370—7.
28.
Fiduccia, C.M. , and R.M. Mattheyses.1982. A linear-time heuristic for improving network partitions . In Proceedings of the IEEE/ACM 19th Design Automation Conference, Las Vegas, NV, pp. 175—81.
29.
Diekmann, R. , B. Monien , and R. Preis.1994. Using helpful sets to improve graph bisections. Technical Report TR-RF-94-008, Department of Computer Science, University of Paderborn , Germany.
30.
Gilbert, J.R. , and E. Zmijewski.1987. A parallel graph partitioning algorithm for a message-passing multiprocessor . International Journal of Parallel Programming16(6): 427—49 .
31.
Berger, M.J. , and B.H. Bokhari.1987. A partitioning strategy for non-uniform problems across multiprocessors . IEEE Transactions on Computers36: 570—80 .
32.
Williams, R.D.1991. Performance of dynamic load balancing algorithms for unstructured mesh calculations . Concurrency: Practice and Experience3: 457—81 .
33.
Fox, G.C.1988. A Review of Automatic Load Balancing and Decomposition Methods for the Hypercube. New York: Springer-Verlag , pp. 63—76.
34.
Farhat, C. , and M. Lesoinne.1993. Automatic partitioning of unstructured meshes for the parallel solutions of problems in computational mechanisms . International Journal for Numerical Methods in Engineering36: 745—64 .
35.
Simon, H.D.1991. Partitioning of unstructured problems for parallel processing . Computing Systems in Engineering2(2—3): 135— 48 .
36.
Pothen, A. , H.D. Simon , and K.P. Liu.1990. Partitioning sparse matrices with eigenvectors of graphs . SIAM Journal on Matrix Analysis and Applications11(3): 430—52 .
37.
Barnes, E.R.1982. An algorithm for partitioning the nodes of a graph . SIAM Journal for Algorithms and Discrete Methods3: 541—50 .
38.
Boppana, R.B.1987. An average case analysis . In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, CA, pp. 67—75.
39.
Hendrickson, B. , and R. Leland.1995. An improved spectral graph partitioning algorithm for mapping parallel computations . SIAM Journal on Scientific Computing16(2): 452—69 .
40.
Banan, M. , and K.D. Hielmstad.1992. Self-organization of architecture by simulated hierarchical adaptive random partitioning . In Proceedings of the International Joint Conference of Neural Networks (IJCNN), Vol. 3, pp. 823—8.
41.
Johnson, D.S. , C.R. Aragon , L.A. McGeoch , and C. Schevon.1989. Optimization by simulated annealing: an experimental evaluation. Part I: Graph partitioning . Operations Research37(6): 865—92 .
42.
den Bout, D.E.V. , and T.K. Miller , III. 1994. Graph partitioning using annealed neural networks . IEEE transaction on Neural Networks1(2): 192—203 .
43.
Rolland, E. , H. Pirkul , and F. Glover.1996. Tabu search for graph partitioning. Annals ofOperations Research63: 209—32 .
44.
Bui, T.N. , and B.R. Moon.1996. Genetic algorithm and graph partitioning . IEEE Transactions on Computers45(7): 841—55 .
45.
Cardellini, V. , M. Colajanni , and P.S. Yu.2003. Request redirection algorithms for distributed web systems . IEEE Transactions on Parallel and Distributed Systems14(1): 355—68 .
46.
Floyd, S. , and V. Paxson.2001. Difficulties in simulating the inter-net . IEEE/ACM Transactions on Networking9(4): 392—403 .
47.
Arlitt, M. , and T. Jin.2000. A workload characterization study of the 1998 World Cup web site . IEEE Network14: 30—7 .
48.
Barford, P. , and M. Crovella.1999. A performance evaluation of hyper text transfer protocols . Proceeding of ACM Sigmetrics27(1): 188—97 .
