Partitioning a call graph

R.H. Bisseling, J. Byrka, S. Cerav-Erbas, N. Gvozdenovic, M. Lorenz, R.A. Pendavingh, C. Reeves, M. Röger, A. Verhoeven

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

Abstract

Splitting a large software system into smaller and more manageable units has become an important problem for many organizations. The basic structure of a software system is given by a directed graph with vertices representing the programs of the system and arcs representing calls from one program to another. Generating a good partitioning into smaller modules becomes a minimization problem for the number of programs being called by external programs. First, we formulate an equivalent integer linear programming problem with 0–1 variables. Theoretically, with this approach the problem can be solved to optimality, but this becomes very costly with increasing size of the software system. Second, we formulate the problem as a hypergraph partitioning problem. This is a heuristic method using a multilevel strategy, but it turns out to be very fast and to deliver solutions that are close to optimal.
Original languageEnglish
Title of host publicationProceedings of the fifty-second European Study Group with Industry (ESGI52/SWI2005, Amsterdam, The Netherlands, January 31-February 4, 2005), CWI Syllabus 55
EditorsJ.B. Berg, van den, S. Bhulai, J. Hulshof, G. Koole, C. Quant, J.F. Williams
Place of PublicationAmsterdam
PublisherCentrum voor Wiskunde en Informatica
Pages95-107
ISBN (Print)90-6196-532-2
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Partitioning a call graph'. Together they form a unique fingerprint.

  • Cite this

    Bisseling, R. H., Byrka, J., Cerav-Erbas, S., Gvozdenovic, N., Lorenz, M., Pendavingh, R. A., Reeves, C., Röger, M., & Verhoeven, A. (2006). Partitioning a call graph. In J. B. Berg, van den, S. Bhulai, J. Hulshof, G. Koole, C. Quant, & J. F. Williams (Eds.), Proceedings of the fifty-second European Study Group with Industry (ESGI52/SWI2005, Amsterdam, The Netherlands, January 31-February 4, 2005), CWI Syllabus 55 (pp. 95-107). Centrum voor Wiskunde en Informatica.