This paper deals with a visualization-based approach to performance analyzing and tuning of highly irregular task-parallel applications. At its core lies a novel automatic layout algorithm for execution graphs which is based on Sugiyama's framework. Our visualization enables the application designer to reliably detect manifestations of parallel overhead and to investigate on their individual root causes. We particularly focus on structural properties of task-parallel computations which are hard to detect in a more analytical way, for example, false sharing and false parallelism. In addition, we discuss embedding our visualization into an integrated development environment, realizing a seamless work-flow for implementation, execution, analysis, and tuning of parallel programs.
MalonyAD. Tools for parallel computing: A performance evaluation perspective. In: BlazewiczJEckerKPlateauBTrystramD (Eds). Handbook on Parallel and Distributed Processing. Springer-Verlag: Berlin, Heidelberg, New York, 2000; chapter 7.
2.
ReedDAAydtRA. Tools for performance tuning and debugging. In: DongarraJFosterIFoxGGroppWKennedyKTorczonLWhiteA (Eds). Sourcebook of Parallel Computing. Morgan Kaufmann Publishers: 2003; chapter 15.
3.
RandallKH. Cilk: Efficient multithreaded computing. PhD thesis, MIT Department of Electrical Engineering and Computer Science, June 1998.
4.
BlochingerWKüchlinWLudwigCWeberA.An object-oriented platform for distributed high-performance Symbolic Computation. Mathematics and Computers in Simulation1999; 49: 161–178.
5.
BlochingerWKüchlinW.The design of an API for strict multithreading in C++. In: KoschHBöszörményiLHellwagnerH (Eds). Proceedings of the Ninth International Conference on Euro-Par 2003 (Klagenfurt, Austria), no. 2790 in LNCS, Springer-Verlag: Berlin, Heidelberg, New York, 2003; 722–731.
6.
SkillicornDBTaliaD.Models and languages for parallel computing. ACM Computing Surveys1998; 30: 123–169.
7.
BlumofeRDLeisersonCE. Space efficient scheduling of multithreaded computations. In: Proceedings of the Twenty Fifth Annual ACM Symposium on Theory of Computing (San Diego, CA), 1993; 362–371.
8.
SugiyamaKTagawaSTodaM.Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics SMC1981; 11: 109–125.
9.
BastertOMatuszewskiC.Layered drawings of digraphs. In: Drawing Graphs: Methods and Models, In: KaufmannMWagnerD (eds.), Chapter 1. Springer: Berlin, Heidelberg, New York, 2001; 87–120.
10.
FrickA.Upper bounds on the number of hidden nodes in sugiyama's algorithm. In: Graph Drawing (GD 96), vol. 1190 of Lecture Notes in Computer Science, Springer, 1997; 169–183.
11.
EiglspergerMSiebenhallerMKaufmannM.An efficient implementation of Sugiyama's algorithm for layered graph drawing. In: Graph Drawing (GD 04), vol. 3383 of Lecture Notes in Computer Science, Springer, 2005; 155–166.
12.
FowlerM.UML Distilled: A Brief Guide to the Standard Object Modeling Language. 3rd edn., Addison-Wesley: Boston, 2004.
13.
GansnerEKoutsofiosENorthSVoK-P.A technique for drawing directed graphs. Software Engineering1993; 19: 214–230.
KraemerEStaskoJ.Creating an accurate portrayal of concurrent executions. Concurrency1998; 6: 36–46.
26.
ZhaoQStaskoJ.Visualizing the execution of threads-based parallel programs. Technical Report GIT-GVU-95–01, Graphics, Visualization, and Usability Center, Georgia Institute of Technology, Atlanta, GA, 1995.
27.
TopolBStaskoJSunderamV.PVaniM: A tool for visualization in network computing environments. Concurrency: Practice and Experience1998; 10: 1197–1222.
28.
BoschRStolteCStollGRosenblumMHanrahanP.Performance analysis and visualization of parallel systems using SimOS and Rivet: A case study. In: Proceedings of the Sixth International Symposium on High-Performance Computer Architecture, 2000; 360–371.
29.
BarthWMutzelPJüngerM.Simple and efficient bilayer cross counting. Journal of Graph Algorithms and Applications, 2004; 8: 179–194.
30.
EadesPSugiyamaK.How to draw a directed graph. Journal of Information Processing1990; 13: 424–437.
31.
EadesPLinX.A new heuristic for the feedback arc set problem. Australian Journal of Combinatorics1995; 12: 15–26.
SugiyamaKMisueK.Visualization of structural information: Automatic drawing of compound digraphs. IEEE Transactions on Systems, Man and Cybernetics1991; 21: 876–892.
WaddleV.Graph layout for displaying data structures. In: MarksJ (Ed). Graph Drawing, Colonial Williamsburg, 2000, Springer, 2001; 241–252.
38.
ForsterM.A fast and simple heuristic for constrained two-level crossing reduction. In: PachJ (Ed). Proceedings of Graph Drawing, GD 2004, vol. 3383 of Lecture Notes in Computer Science, Springer: Berlin, Heidelberg, New York, 2005; 206–216.
39.
FriedrichCSchreiberF.Flexible layering in hierarchical drawings with nodes of arbitrary size. In: CRPIT ′04: Proceedings of the 27th conference on Australasian computer science (Darlinghurst, Australia, 2004), Australian Computer Society, Inc., 2004; 369–376.
40.
SeemannJ.Extending the Sugiyama algorithm for drawing UML class diagrams: Towards automatic layout of object-oriented software diagrams. In: DiBattistaG (Ed). Proceedings Graph Drawing, 5th International Symposium, GD ′97, Rome, Italy, September, 1997, vol. 1353, Springer: Berlin, Heidelberg, New York, 1997.
BrandesUDwyerTSchreiberF.Visualizing related metabolic pathways in two and a half dimensions. In: LiottaG (Ed). Graph Drawing, Perugia, 2003, Springer: Berlin, Heidelberg, New York, 2004; 111–22.
46.
SanderG.Graph layout for applications in compiler construction. Theoretical Computer Science1999; 217: 175–214.
