*************************** SPAA'96 ********************** 8th Annual ACM Symposium on Parallel Algorithms and Architectures Padua, Italy June 24 -- 26, 1996 Sponsored by ACM SIGACT and ACM SIGARCH In Cooperation with EATCS For more information see http://www.cs.jhu.edu/Conferences/SPAA/ or send mail to: spaa96@artemide.dei.unipd.it ********************************************************** GENERAL INFORMATION SPAA'96 will be held in Padua, a charming historical city, home to one of the oldest (1222) and most prestigious universities in Europe. Four centuries ago, Galileo came here as a Professor of Mathematics to spend, in his own words, ``the best 18 years of my life''. Padua's surroundings include a number of world-famous tourist attractions such as Venice, Verona, and the Dolomites. In June, typical temperatures are in the mid-20's C (upper-70's F), cooling down in the evening. Approximate Exchange Rate: USD 1 = Lit. 1,600. TRANSPORTATION The most convenient airport to reach Padua is Venice (30 miles from Padua), serviced by most European airlines. Some airlines, however, only fly to Milan's airports (about 150 miles from Padua). From Venice's Marco Polo Airport to Padua: Taxi: Approximately Lit. 120,000 per ride. Limousine: To be reserved at least one day in advance by specifying name, flight number, arrival time, and destination within Padua, with one of the following companies: Landomas, Lit. 35,000 per person. Identify yourself as a SPAA'96 attendee to obtain this rate. Phone: +39-49-8601426 and +39-49-8600819. Fax: +39-49-8601642. Coop. Radio Taxi, Air Service, Lit. 37,000 per person. Phone: +39-49-651333. Fax: +39-49-8758550. Bus to Venice + Bus/Train to Padua: Take bus No. 5 at the airport (tickets purchased in advance inside the airport). The bus leaves every 30 minutes from 7:10 a.m. to 11:10p.m.; it will take you to Piazzale Roma, which is in the heart of Venice and close to both the bus terminal and the train station. From Piazzale Roma to Padua there are three options, each costing approximately Lit. 15,000: ATP Bus or SITA Bus: leaves every 30 minutes and takes about 45 minutes; the last one is at 9:30 p.m. ACTV Bus: leaves every 30 minutes and takes 1 hour and 10 minutes; the last one is at 11:45 p.m. It goes via the Brenta Riviera, near some remarkable Venetian villas. Train: the train station in Venice is within walking distance from Piazzale Roma, but one can also take a ferry (No. 1 or 82). Trains leave about every half hour and take 30 minutes. The last train leaves at 10:35 p.m. From Milan's Linate and Malpensa Airports to Padua: From either airport, one can take a bus or a taxi to reach the train station Milano Centrale. Buses leave every 20 minutes or so; tickets are sold inside the airport for Lit. 12,000. Trains from Milan to Padua-Venice are rather frequent (about every 2 hours) and take about 2 hours and 30 minutes. The last train leaves at 9:05 p.m. Cost depends on class (first or second) and type of train, but it is quite reasonable. From Rome: If you land in Rome and do not continue on a connecting flight to Venice, it will take about 5 hours to reach Padua by train. Roma Termini, the main train station, can be easily reached from Fiumicino Airport by a shuttle train (Lit. 10,000). The last regular train to Padua leaves Rome at 5:15 p.m. A more expensive, faster train (called ``Pendolino'' and requiring advance reservation) leaves at 6:45 p.m. and takes less than four hours. ACCOMODATIONS Blocks of rooms have been reserved at the downtown hotels listed below. Rooms and rates are guaranteed until April 30. Thereafter, reservations are subject to availability. Since June is peak season in Padua for both commercial and touristic events, early reservations are strongly recommended. Hotel Plaza, Corso Milano 40, I-35139 Padova, Tel: +39 49 656822, Fax: +39 49 661117, Lit. 160,000 (Single), Lit. 230,000 (Double), breakfast included. Five minutes walk to the conference site. Hotel Europa, Largo Europa 9, I-35137 Padova, Tel: +39 49 661200, Fax: +39 49 661508, Lit. 132,000 (Single), Lit. 178,000 (Double), breakfast included. Five minutes walk to the conference site. Hotel Milano, Via Pilade Bronzetti 62 (near Piazzale Savonarola), I-35138 Padova, Tel: +39 49 8712555, Fax: +39 49 8713923, Lit. 120,000 (Single), Lit. 150,000 (Double), breakfast included. Ten minutes walk to the conference site. Hotel Igea, Via Ospedale 87, I-35100 Padova, Tel: +39 49 8750577, Fax: +39 49 660865, Lit. 75,000 (Single), Lit. 95,000 (Double). Breakfast available upon request (add Lit. 10,000). Fifteen minutes walk to the conference site. All rates include taxes. Advance payment is not required and major credit cards are accepted by all of the hotels. When making the reservation, please remember to identify yourself as a SPAA'96 attendee. Reservations by fax have to be confirmed by a fax reply. ********************************************************** CONFERENCE REGISTRATION FORM ********************************************************** Name (first, last): Name tag should read: Affiliation: Address: Phone: Fax: Internet address: Check your dietary preference: Vegetarian No Restriction Please indicate any special needs: Conference registration includes the proceedings, welcome reception, business meeting, lunches on Monday and Wednesday, banquet on Tuesday evening (except student registration), coffee breaks, and guided tour of Palazzo del Bo'. The deadline for early registration is May 24, 1996. (But register with hotels before April 30.) Please circle selection and fill in your ACM membership number, if appropriate: Registration Early Late ACM member $295 (Lit. 472,000) $345 (Lit. 552,000) Non-member $370 (Lit. 592,000) $420 (Lit. 672,000) Student $130 (Lit. 208,000) $160 (Lit. 256,000) Additional Tickets: Number Amount Reception ($25 or Lit. 40,000 each) | | | Lunch ($25 or Lit. 40,000 each) | | | Banquet ($40 or Lit. 64,000 each) | | | TOTAL: ********************************************************** If paying by VISA card (in Italian Lire), please complete: VISA Card Number: Expiration Date: Signature: Please include a completed registration form with your payment. Fees can be paid in three ways: Check (in U.S. dollars drawn on a U.S. or Canadian bank): Make check payable to ACM SPAA and mail to Bruce Maggs School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 (bmm@cs.cmu.edu) Check (in Italian Lire drawn on an Italian bank): Make check payable to ``Consorzio Padova Ricerche - SPAA'96'' and mail to Consorzio Padova Ricerche - SPAA'96 Corso Spagna, 12 35020, Padova, Italy VISA (in Italian Lire): Mail registration form, including VISA card number, expiration date and (original) signature to Consorzio Padova Ricerche - SPAA'96 at the same address given above. ********************************************************** SPAA'95 and SPAA'96 PROCEEDINGS Proceedings for SPAA'95 and SPAA'96 can be purchased for $25 and $40, respectively, by sending a check payable to ACM SPAA to Bruce Maggs School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 (bmm@cs.cmu.edu) ********************************************************** LOCATION OF EVENTS AND HOTELS Conference and lodging facilities are all within a small radius in the heart of the city. See the formatted version (postscript) of the advance program for a map. Registration/Reception: Hotel Plaza, Corso Milano 40 Technical Program and Business Meeting: Camera di Commercio, Via E. Filiberto 34 Monday and Wednesday Lunch: Ristorante Zaramella, Largo Europa 10 Banquet: Directions will be given at the conference. Tuesday Lunch, Monday and Wednesday Dinners (unstructured): A list of restaurants will be provided. CURRENCY EXCHANGE Exchange bureaus can be found at local banks; banks are closed from 1:30 p.m. to 2:30 p.m. and after 3:30 p.m. on weekdays and throughout weekends. SUMMER SCHOOL The week before SPAA'96 (June 17-12), there will be a Summer School in Padua on Architectures and Programming Paradigms for Parallel Computing. Fellowships will be available on a competitive basis. Information will be posted on theorynet and other newsgroups. ********************************************************** CONFERENCE SCHEDULE ********************************************************** SUNDAY, JUNE 23, 1996 6:00 Conference registration (Hotel Plaza) 7:00 Conference reception (Hotel Plaza) ********************************************************** MONDAY, JUNE 24, 1996 ********************************************************** SESSION 1 9:00 Towards Efficiency and Portability: Programming with the BSP Model Mark Goudreau, U. Central Florida Kevin Lang, Satish Rao, Torsten Suel, NEC Thanasis Tsantilas, Columbia U. 9:25 A Quantitative Comparison of Parallel Computation Models Harry A.G. Wijshoff, B.H.H. Juurlink, Leiden U. 9:50 BSP vs LogP Gianfranco Bilardi, U. Padova and U. Illinois, Chicago; Kieran T. Herley, U. College Cork; Andrea Pietracaprina, Geppino Pucci, U. Padova; Paul Spirakis, Computer Technology Institute, Patras 10:15 Break SESSION 2 10:45 A Steady State Analysis of Diffracting Trees Nir Shavit, Tel-Aviv U. and MIT; Eli Upfal, IBM Almaden and Weizmann Institute; Asaph Zemach, Tel-Aviv U. 11:10 Asynchronous Shared Memory Search Structures Micah Adler, UC Berkeley and ICSI 11:35 Improved Methods for Hiding Latency in High Bandwidth Networks Matthew Andrews, Tom Leighton, MIT; P. Takis Metaxas, Wellesley College; Lisa Zhang, MIT 12:00 Optimal Latency-Throughput Tradeoffs for Data Parallel Pipelines Jaspal Subhlok, CMU; Gary Vondran, HP Labs 12:40 Lunch (Ristorante Zaramella) SESSION 3 2:30 First and Second Order Diffusive Methods for Rapid, Coarse, Distributed Load Balancing Bhaskar Ghosh, Informix; S. Muthukrishnan, U. Warwick; Martin H. Schultz, Yale 2:55 On Multiprocessor System Scheduling Xiaotie Deng, Patrick Dymond, York U. 3:20 An Analysis of Gang Scheduling for Multiprogrammed Parallel Computing Environments Mark Squillante, IBM T.J. Watson; Fang Wang, Yale; Marios Papaefthymiou, Yale 3:45 Break SESSION 4 4:15 Flexible Usage of Parity Storage Space in Disk Arrays Eric J. Schwabe, Ian M. Sutherland, Northwestern 4:40 Simple Randomized Mergesort on Parallel Disks Rakesh D. Barve, Duke; Edward F. Grove, Max-Planck-Institut, Saarbrucken; Jeffrey Scott Vitter, Duke 5:05 Anticipatory Instruction Scheduling Vivek Sarkar, Barbara Simons, IBM Software Solutions Division 5:45 Business Meeting (Camera di Commercio) ********************************************************** TUESDAY, JUNE 25, 1996 ********************************************************** 9:00 Vishkin, U. Maryland, College Park 10:15 Break SESSION 5 10:45 On the Benefit of Supporting Virtual Channels in Wormhole Routers Richard J. Cole, Courant Institute, NYU; Bruce M. Maggs, CMU; Ramesh K. Sitaraman, U. Massachusetts, Amherst 11:10 Universal Continuous Routing Strategies Christian Scheideler, Berthold Vocking, Heinz Nixdorf Institut, Paderborn 11:35 On the Communication Throughput of Buffered Multistage Interconnection Networks Ralf Rehrmann, Burkhard Monien, Reinhard Luling, Ralf Diekmann, U. Paderborn 12:00 Constant Time per Edge is Optimal on Rooted Tree Networks Michael Mitzenmacher, UC Berkeley 12:40 Lunch SESSION 6 2:30 A Tight Layout of the Butterfly Network Aythan Avior, Technion; Tiziana Calamoneri, U. Rome ``La Sapienza''; Shimon Even, Technion; Ami Litman, Technion; Arnold L. Rosenberg, U. Massachussetts, Amherst 2:55 On the Slowdown of Efficient Simulations of Multibutterflies on Butterflies and Butterfly-Derived Networks Kevin J. Rappoport, Pacific-Sierra Research 3:20 Local Memory Requirement of Universal Routing Schemes P. Fraigniaud, C. Gavoille, LIP ENS Lyon 3:45 Break Session 7 (Research Summaries) 4:15 A Dynamic Load Balancing Framework for Unstructured Adaptive Computations on Distributed-Memory Multiprocessors Andrew Sohn, NJIT; Rupak Biswas, RIACS; Horst D. Simon, Lawrence Berkeley Labs. 4:30 A Library of Basic PRAM Algorithms and its Implementation in FORK Christoph W. Kess ler, U. Trier; Jesper Larsson Traff, Max-Planck Institut fur Informatik 4:45 uDatabase: Parallelism in a Memory-Mapped Environment Peter Buhr, Anil Goel, Naomi Nishimura, Prabhakar Ragde, U. Waterloo 5:00 From AAPC Algorithms to High Performance Permutation Routing and Sorting Thomas M. Stricker, Jonathan C. Hardwick, CMU 5:15 Parallel Neighborhood Modeling D. Hutchinson, L. Kuttner, M. Lanthier, A. Maheshwari, D. Nussbaum, D. Roytenberg, J. R. Sack, Carleton U. 5:30 Components of Congestion Control Ludmila Cherkasova, HP Labs; Al Davis, U. Utah; Robin Hodgson, Vadim Kotov, Ian Robinson, Tomas Rokicki, HP Labs 8:00 Banquet ********************************************************** WEDNESDAY, JUNE 26, 1996 ********************************************************** Session 8 9:00 Parallel Algorithms for Personalized Communication and Sorting with an Experimental Study David R. Helman, David A. Bader, Joseph JaJa, U. Maryland, College Park 9:25 Deterministic Sorting and Randomized Median Finding on the BSP Model Alexandros V. Gerbessiotis, Constantinos J. Siniolakis, Oxford 9:50 Fully Dynamic Search Trees for an Extension of the BSP Model Armin Baumker, Wolfgang Dittrich, U. Paderborn 10:15 Break SESSION 9 10:45 Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling Richard Cole, Courant Institute, NYU; Philip N. Klein, Brown; Robert E. Tarjan, Princeton 11:10 Parallel Multidimensional Search Using Approximation Algorithms: With Applications to Linear-Programming and Related Problems Sandeep Sen, IIT New Delhi 11:35 Parallel Balanced Allocations Volker Stemann, ICSI 12:00 Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems Yonatan Aumann, Bar-Ilan U.; Michael A. Bender, Harvard; Y. Lisa Zhang, MIT 12:40 Lunch (Ristorante Zaramella) SESSION 10 2:30 Scope Consistency: A Bridge Between Release Consistency and Entry Consistency Liviu Iftode, Jaswinder Pal Singh, Kai Li, Princeton 2:55 Verification of FLASH Cache Coherence Protocol by Aggregation of Distributed Transactions Seungjoon Park, David L. Dill, Stanford 3:20 An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms Robert D. Blumofe, U. Texas, Austin; Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall, MIT 3:45 Break SESSION 11 4:15 On Trading Task Reallocation for Thread Management in Partitionable Multiprocessors Lixin Gao, Arnold L. Rosenberg, Ramesh K. Sitaraman, U. Massachusetts, Amherst 4:40 Load-Sharing via Weighted Factoring Susan Flynn Hummel, Polytechnic U. and IBM T.J. Watson; Jeanette Schmidt, R.N. Uma, Joel Wein, Polytechnic U. 5:05 Resource Scheduling for Parallel Database and Scientific Applications Soumen Chakrabarti, UC Berkeley; S. Muthukrishnan, U. Warwick 6:00 Guided Tour of Palazzo del Bo' ********************************************************** SPAA'96 ORGANIZATION ********************************************************** Conference Chair Charles E. Leiserson, MIT Local Arrangements Committee Gianfranco Bilardi (Chair), Concettina Guerra, Massimo Maresca, Andrea Pietracaprina, Marinella Pines, Geppino Pucci, Universita di Padova. Conference Treasurer Bruce Maggs, CMU Conference Secretary Robert Cypher, Johns Hopkins Program Chair Guy E. Blelloch, CMU Program Committee Roberto Bisiani, U. Milan Robert Cypher, Johns Hopkins Phil Gibbons, AT&T Bell Labs Thomas Gross, CMU and ETH Zurich F. Meyer auf der Heide, U. Paderborn Christopher Jesshope, U. Surrey Bill McColl, Oxford Vijaya Ramachandran, U. of Texas John Reif, Duke Horst Simon, Lawrence Berkeley Labs. Larry Snyder, U. Washington Kathy Yelick, UC Berkeley PATRONS The following institutions have provided generous support: - Camera di Commercio Industria Artigianato ed Agricoltura di Padova - Comune di Padova - Consiglio Nazionale delle Ricerche - Consorzio Padova Ricerche - Information Technology Program of the European Union - Universita di Padova CORPORATE AFFILIATES - Cambridge University Press - Elsevier Science Publishers - Morgan Kaufmann Publishers - Plenum Publishers - SIAM