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

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 proceeding › Conference contribution › Academic

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 language	English
Title of host publication	Proceedings of the fifty-second European Study Group with Industry (ESGI52/SWI2005, Amsterdam, The Netherlands, January 31-February 4, 2005), CWI Syllabus 55
Editors	J.B. Berg, van den, S. Bhulai, J. Hulshof, G. Koole, C. Quant, J.F. Williams
Place of Publication	Amsterdam
Publisher	Centrum voor Wiskunde en Informatica
Pages	95-107
ISBN (Print)	90-6196-532-2
Publication status	Published - 2006

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.

Bisseling, R.H. ; Byrka, J. ; Cerav-Erbas, S. et al. / Partitioning a call graph. Proceedings of the fifty-second European Study Group with Industry (ESGI52/SWI2005, Amsterdam, The Netherlands, January 31-February 4, 2005), CWI Syllabus 55. editor / J.B. Berg, van den ; S. Bhulai ; J. Hulshof ; G. Koole ; C. Quant ; J.F. Williams. Amsterdam : Centrum voor Wiskunde en Informatica, 2006. pp. 95-107

@inproceedings{d8b17386030b4cafbbbdc1da04e65d2f,

title = "Partitioning a call graph",

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.",

author = "R.H. Bisseling and J. Byrka and S. Cerav-Erbas and N. Gvozdenovic and M. Lorenz and R.A. Pendavingh and C. Reeves and M. R{\"o}ger and A. Verhoeven",

year = "2006",

language = "English",

isbn = "90-6196-532-2",

pages = "95--107",

editor = "{Berg, van den}, J.B. and S. Bhulai and J. Hulshof and G. Koole and C. Quant and J.F. Williams",

booktitle = "Proceedings of the fifty-second European Study Group with Industry (ESGI52/SWI2005, Amsterdam, The Netherlands, January 31-February 4, 2005), CWI Syllabus 55",

publisher = "Centrum voor Wiskunde en Informatica",

}

Bisseling, RH, Byrka, J, Cerav-Erbas, S, Gvozdenovic, N, Lorenz, M, Pendavingh, RA, Reeves, C, Röger, M & Verhoeven, A 2006, Partitioning a call graph. in JB Berg, van den, S Bhulai, J Hulshof, G Koole, C Quant & JF 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. Centrum voor Wiskunde en Informatica, Amsterdam, pp. 95-107.

Partitioning a call graph. / Bisseling, R.H.; Byrka, J.; Cerav-Erbas, S. et al.
Proceedings of the fifty-second European Study Group with Industry (ESGI52/SWI2005, Amsterdam, The Netherlands, January 31-February 4, 2005), CWI Syllabus 55. ed. / J.B. Berg, van den; S. Bhulai; J. Hulshof; G. Koole; C. Quant; J.F. Williams. Amsterdam: Centrum voor Wiskunde en Informatica, 2006. p. 95-107.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - Partitioning a call graph

AU - Bisseling, R.H.

AU - Byrka, J.

AU - Cerav-Erbas, S.

AU - Gvozdenovic, N.

AU - Lorenz, M.

AU - Pendavingh, R.A.

AU - Reeves, C.

AU - Röger, M.

AU - Verhoeven, A.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 90-6196-532-2

SP - 95

EP - 107

BT - Proceedings of the fifty-second European Study Group with Industry (ESGI52/SWI2005, Amsterdam, The Netherlands, January 31-February 4, 2005), CWI Syllabus 55

A2 - Berg, van den, J.B.

A2 - Bhulai, S.

A2 - Hulshof, J.

A2 - Koole, G.

A2 - Quant, C.

A2 - Williams, J.F.

PB - Centrum voor Wiskunde en Informatica

CY - Amsterdam

ER -

Bisseling RH, Byrka J, Cerav-Erbas S, Gvozdenovic N, Lorenz M, Pendavingh RA et al. Partitioning a call graph. In Berg, van den JB, Bhulai S, Hulshof J, Koole G, Quant C, Williams JF, editors, Proceedings of the fifty-second European Study Group with Industry (ESGI52/SWI2005, Amsterdam, The Netherlands, January 31-February 4, 2005), CWI Syllabus 55. Amsterdam: Centrum voor Wiskunde en Informatica. 2006. p. 95-107

Partitioning a call graph

Abstract

Fingerprint

Cite this