The design and analysis of efficient data structures has long been recognized as a key component of the Computer Science curriculum. Goodrich and Tomassia's approach to this classic topic is based on the object-oriented paradigm as the framework of choice for the design of data structures.
The 10th International Symposium on Graph Drawing (GD 2002) was held on August 26-28,2002,at Irvine,California. The conference attracted 74 parti- pants from academic and industrial institutions in 14 countries. As in previous years,the review process was 24 out of 48 regular submissions were accepted. In addition,9 short papers and 8 system demonst- tions (1 withdrawn) were also accepted. Each submission was refereed by at least 4 members of the program committee,and detailed comments were returned to the authors. GD 2002 invited two Frank Ruskey,from the University of Victoria, gave a talk on drawing Venn diagrams; James Arvo,from the California Institute of Technology,gave a talk on techniques for interactive graph drawing. As usual,the Graph Drawing contest was held during the conference. The report on the contest is included in the proceedings. We would like to thank all the people who helped organize and run the conference. We would like to thank our ILOG,MERL (Mitsubishi Electric Research Laboratories),sd&m (Software Design & Management),Tom Sawyer Software,and the University of California,Irvine. We would also like to thank all the contributors and participants who made GD 2002 a success. The 11th International Symposium of Graph Drawing (GD 2003) will be held on September 21-24,2003 at Perugia,Italy,with Giuseppe Liotta as the conference chair.
Symmetric multiprocessors (SMPs) are dominant in the high-end server market and are key for large-scale multiprocessor systems. However, designing efficient parallel algorithms for this platform presents challenges due to the rapid increase in microprocessor speed, which has made main memory access the main performance bottleneck. Consequently, merely increasing the number of processors does not guarantee improved performance, as memory bus limitations typically restrict SMPs to 16 processors. This situation has two implications for algorithm designers: first, parallel algorithms must compete effectively with their sequential counterparts using as few as one processor; second, to scale well with the number of processors, algorithms must minimize both the number and type of main memory accesses. This paper introduces a computational model for developing efficient algorithms for symmetric multiprocessors. Using this model, we derive efficient solutions for two distinct problem types: linked list prefix computations and generalized sorting. Both problems are memory-intensive but differ in their access patterns. Generalized sorting algorithms often require numerous memory accesses to contiguous locations, while prefix computation algorithms need fewer accesses, typically to non-contiguous memory locations.