A more refined visualization

Mesh(Out P, Out 1) Assign P = side;

MeshProcessorItems(Out 2,1);

MeshItemValue(I,J,K,Out Int,Out V,1) If K==1 Assign V = data[index(I,J)];

Moreover If K==2 Assign V = aux[index(I,J)];

**/

The first predicate declares a mesh with identification number 1 whose sidePis equal to the content of the C variableside. Each processor(I,J) in the mesh maintains two local values, as declared by MeshProcessorItems. Both items store integer values, equal to data[index(I,J)] and to aux[index(I,J)], respectively. These declarations are sufficient to create a basic visualization:

each time the content of any of the variablesside,data, orauxis changed by the underlying program computation, the visualization of the mesh is updated accordingly.

4.4 A more refined visualization

The students were not satisfied by such a simple visualization, because it does not clearly convey which processors are operating at each instant, which ones are sending information, and which ones are receiving it. The use of colors and of other graphical features was identified by the students as a proper mean to obtain the desired effect.

The refined visualization has required introducing an auxiliary integer variable, namedstep. This variable maintains the number of the current step of the algorithm, and can be either 1 or 2 or 3 (see the algorithm explanation in Section 3.1). The following additional declarations use variablestepto produce the more refined visualization:

/**

MeshItemColor(I,J,1,Out Cyan,1) If (step==1 && J==j);

MeshItemColor(I,J,K,Out Col,1)

If (step==2 && I==i && J==side-1) || (step==3 && J==j) Assign Col = (K==1) ? Cyan : LightGrey;

MeshLineColor(L, Out Red ,1)

If step==1 && j<side && (j-1)*side<=L && L<j*side;

MeshLineColor(L, Out Blue,1)

If step==2 && i<side && L==side*(side-1)+i*side-1;

MeshLineColor(L, Out Red ,1)

If step==3 && j<side && j*side<=L && L<(j+1)*side;

MeshLineThickness(L,Out Thick,1)

For Color: MeshLineColor(L,Color,1) If Color==Red || Color==Blue;

**/

The first two predicates are used to color the active processors. In particular, during the first step, the underlying program propagates information left to right in theuvalues, letting the column index jincrease from0toside-1. Hence, the first definition of predicateMeshItemColorassignsCyan color to the u value managed by processor(I,J)if step==1and the processor is in the currently active column j(i.e.,J=j). Since no test is performed on parameterI, the predicate holds for each value ofI. Similar conditions are imposed to color processors during the other steps.

The remaining predicates are used for highlighting the active communication links at any step.

Here we need to recall that communication links among processors are indexed as in Figure 1(c):

numbers from 0 toside∗(side−1)−1 are devoted to horizontal links and numbers fromside∗(side−1) to 2∗side∗(side−1)−1 to vertical ones. Based on this numbering, during the first step, as long as the C variablejis smaller than the mesh side, a linkLhasRedcolor if(j-1)*side≤L<j*side.

It is easy to see that the previous condition identifies all the horizontal links between processors in columns j−1 andj, respectively: for instance, in the mesh with side 3 given in Figure 1(c), when j=2=side-1links 3, 4, and 5 are highlighted. Similar considerations hold for coloring links in the sec-ond and third steps. Moreover, all red and blue colored links have thick size, as asserted by predicate MeshLineThickness.

We finally need to show how visual events are linked to the source code. Due to the lack of space we consider only the first step of the algorithm, the code for the other steps being similar. We recall that in Leonardo visual events are automatically detected by the system each time the content of a data structure changes. Hence, in order to highlight correctly the parallel steps, it is crucial to identify points of the source code where the visualization must beturned off: in this way, when the visualization is turned on again, all the changes that took place meanwhile are visualized at the same time, even if data structures have been progressively modified by the algorithm in consecutive sequential steps.

The visualization can be turned on and offby means of predicateScreenUpdateOn:

step=1;

for (j=1; j<side; j++) {

/** Not ScreenUpdateOn; **/

for (i=0; i<side; i++) data[index(i,j)] += data[index(i,j-1)];

/** ScreenUpdateOn; **/

}

Thanks to the use of predicateScreenUpdateOn, the innerforcycle in the piece of code above will be visualized as a single parallel step, producing the effect that all the items in a fixed columnj have been changed simultaneously.

Acknowledgments

We would like to thank all the students who took part in the experimentation for their enthusiasm and their active participation.

References

R. Ben-Bassat Levy, M. Ben-Ari, and P.A. Uronen. An extended experiment with JEliot 2000. In Proceedings of the 1st Program Visualization Workshop (PVW’00), pages 131–140. University of Joensuu, 2000.

M.H. Brown and M. Najork. Collaborative Active Textbooks: a Web-Based Algorithm Animation System for an Electronic Classroom. InProceedings of the 12th IEEE Symposium on Visual Lan-guages (VL’96), pages 266–275, 1996.

G. Cattaneo, U. Ferraro, G.F. Italiano, and V. Scarano. Cooperative Algorithm and Data Types An-imation over the Net. InProc. XV IFIP World Computer Congress, Invited Lecture, pages 63–80, 1998. System Home Page:http://isis.dia.unisa.it/catai/.

P. Crescenzi, C. Demetrescu, I. Finocchi, and R. Petreschi. Reversible execution and visualization of programs with Leonardo. Journal of Visual Languages and Computing, 11(2):125–150, 2000.

System home page:http://www.dis.uniroma1.it/˜demetres/Leonardo/.

C. Demetrescu and I. Finocchi. The Leonardo user manual, 2000. Available at http://www.dis.uniroma1. it/˜demetres/Leonardo/Documentation.html.

C. Demetrescu and I. Finocchi. Smooth animation of algorithms in a declarative framework. Journal of Visual Languages and Computing, 12(3):253–281, 2001. Special Issue devoted to selected papers from the 15th IEEE Symposium on Visual Languages (VL’99).

J. Domingue and P. Mulholland. Teaching Programming at a Distance: The Internet Software Visualization Laboratory. Journal of Interactive Media in Education, 7, 1997. Available at http://www-jime.open. ac.uk/97/1/.

J. J´aj´a. An Introduction to Parallel Algorithms. Addison Wesley, 1992.

C.M. Kehoe and J.T. Stasko. Using animations to learn about algorithms: An ethnographic case study.

Technical report, Georgia Institute of Technology, Atlanta, Tech. Rep. GIT-GVU-96-20, 1996.

A.W. Lawrence. Empirical Studies of the Value of Algorithm Animation in Algorithm Understanding.

PhD thesis, Georgia Institute of Technology, Atlanta, 1993.

A.W. Lawrence, A.N. Badre, and J.T. Stasko. Empirically Evaluating the Use of Animations to Teach Algorithms. InProceedings of the 10th IEEE International Symposium on Visual Languages (VL’94), pages 48–54, 1994.

R.E. Mayer. Systematic thinking fostered by illustrations in scientific text. Journal of Educational Psychology, 81(2):240–246, 1989.

S. Palmiter and J. Elkerton. An evaluation of animated demonstrations for learning computer-based tasks. InProceedings of the ACM SIGCHI’91 Conference on Human Factors in Computing Systems, pages 257–263, 1991.

R. Petreschi.Notes from the course on parallel algorithms (in Italian). Available at the URLhttp://

cesare.dsi.uniroma1.it/˜asd/asd.html.

M. Pressley. Imagery and children’s learning: Putting the picture in developmental perspective.Review of Educational Research, 47(4):585–622, 1977.

L.P. Rieber, M.J. Boyce, and C. Assad. The effects of computer animation on adult learning and retrieval tasks.Journal of Computer Based Instruction, 17(2):46–52, 1990.

G.C. Roman, K.C. Cox, C.D. Wilcox, and J.Y Plun. PAVANE: a System for Declarative Visualization of Concurrent Computations. Journal of Visual Languages and Computing, 3:161–193, 1992.

J.T. Stasko. TANGO: A Framework and System for Algorithm Animation. Computer, 23:27–39, 1990.

J.T. Stasko. Using Student-Built Algorithm Animation as Learning Aids. InProceedings of the ACM SIGCSE Conference, pages 25–29, 1997.

J.T. Stasko, A.N. Badre, and C. Lewis. Do algorithm animations assist learning? An empirical study and analysis. In Proceedings of the INTERCHI’93 Conference on Human Factors in Computing Systems, pages 61–66, 1993.

J.T. Stasko, J. Domingue, M.H. Brown, and B.A. Price. Software Visualization: Programming as a Multimedia Experience. MIT Press, Cambridge, MA, 1997.

Using Hands-On Visualizations to Teach Computer Science from