6th Annual ACM Symposium on Parallel Algorithms and Architectures Advanced Program __________________________________________________________________________ SPAA'94 6th Annual ACM Symposium on Parallel Algorithms and Architectures Cape May, New Jersey June 26 -- 29, 1994 ACM's 24th International Computer Chess Championship June 25 -- 27, 1994 Sponsored by ACM SIGACT and ACM SIGArch In Cooperation with EATCS Registration for SPAA'94 The registration fees for SPAA'94 are listed below. To qualify for the early registration fee, your registration application must be postmarked by **Friday, May 20**. Refund requests will be honored until June 15. The nonstudent registration fee includes the Sunday night reception, the Monday night business meeting, the Tuesday night banquet, coffee breaks and lunches, and a copy of the proceedings. The student fee includes all of the above except the banquet. Please fill out the form below and send it, along with a check or money order made payable to "SPAA'94," to: SPAA'94 c/o Yuh-dauh Lyuu, Satish Rao NEC Research Institute 4 Independence Way Princeton, NJ 08540 Name _________________________________________________________ Affiliation ________________________________________________________ Street Address ________________________________________________________ City ____________________ State ___________________________ ZIP or Postal # ___________________ Country _____________________________ Internet address _____________________________ Phone _____________________________ Please circle one, and fill in your membership number, if appropriate: Category Fee After 5/20 ACM, SIGACT or SIGArch member 285 335 EATCS member 285 335 Author or Program Committee member 285 335 Student 130 150 Other 345 395 Check your dietary preference: Vegetarian __________________ No Restriction ___________ If you are interested in a shuttle from Philadelphia Airport or Atlantic City Airport, please see information later in this brochure under Transportation, and indicate time and location of flights below or e-mail spaa94@research.nj.nec.com. -------------------------- Arriving flight __________________________________________________________ Departing flight ________________________________________________________ Hotel Reservations The conference will be held at the Grand Hotel in Cape May. The rates for SPAA'94 are posted below and apply from Friday, June 24 through Thursday, June 30. Checkin time is 2 p.m. and checkout is 11 a.m. Arrivals earlier than 2 p.m. will be accommodated as rooms become available. Please advise the hotel of late arrival. Reservations should be made by ***Friday, May 20***. Reservations made after that will be accepted on a rate and space availability basis. To make your reservations by phone, call the Grand Hotel at 609-884-5611 or 800-257-8550 and refer to SPAA'94. To make reservations by mail, fill out the form below and send it to the address below. A deposit in the form of a check or money order for one night's stay or credit card information must be included. When filling out the form, make sure that you list your name exactly as it appears on your check or credit card. The following credit cards are accepted: American Express, Diners Club, Visa, and Mastercard. If you cancel and notify the hotel at least two weeks before your specified arrival, 75 percent of your deposit will be refunded. For babysitting service request, please indicate ages of the children and the times on the form below. The Grand Hotel ATTN: SPAA'94 Reservations P.O. Box 496 Cape May, New Jersey 08204 Fax: 609-898-0341 Single $100 ____________ Double (1 bed) $100 ____________________ Double (2 beds) $100 ____________ Triple $110 ____________________ Quad $120 _____________ Check-in date __________________ Check-out date ____________________ Name ___________________________________________________ Address ___________________________________________________ Phone ___________________________________________________ Sharing room with __________________________________________________ Babysitting requests (times/child's age) ___________________________ If paying for deposit by credit card, please complete: Credit Card Number ___________________________ Credit Card Type _______________ Expiration Date _____________ I authorize The Grand Hotel of Cape May to charge the above account an amount equal to one night's stay as deposit. Signature ______________________________ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% SATURDAY, JUNE 25, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [11:00] Round 1 of the International Computer Chess Championship [7:00] Round 2 of the International Computer Chess Championship %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% SUNDAY, JUNE 26, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [9:30] Round 3 of the International Computer Chess Championship [4:00] Technical Session on Recent Developments in Computer Chess [5:00] Break [7:00] Round 4 of the International Computer Chess Championship [7:00] Conference reception for all SPAA attendees %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% MONDAY, JUNE 27, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [8:00] Continental Breakfast [8:45] Welcoming Remarks by SPAA'94 Organizers Session A [9:00] An Optimal Randomized Logarithmic Time Connectivity Algorithm for the EREW PRAM Shay Halperin, Uri Zwick, Tel Aviv U. [9:20] A Linear-Work Parallel Algorithm for Finding a Minimum Spanning Tree Richard Cole, NYU; Philip N. Klein, Brown; Robert E. Tarjan; Princeton and NEC [9:40] A Comparison of Parallel Algorithms for Connected Components John Greiner, CMU [10:00] Discussion %--------------------------------------------------------------------- [10:20] Break %--------------------------------------------------------------------- Session B [10:50] Improved Bounds for Routing and Sorting on Multi-Dimensional Meshes Torsten Suel, U. Texas, Austin [11:10] 2d-Bubblesorting in O(\sqrt(N \lg N)) Time in the Average Case Doug Ierardi, USC [11:30] Parallel Sorting by Overpartitioning Hui Li, Kenneth C. Sevcik, Toronto [11:50] Discussion %--------------------------------------------------------------------- [12:10] Lunch %--------------------------------------------------------------------- Session C [1:40] Efficient Compilation of High-Level Data Parallel Algorithms Dan Suciu, Val Tannen, U. Pennsylvania [2:00] SIMD Instruction Cache Todd E. Rockoff, Flinders U. [2:20] Improved Parity-Declustered Layouts for Disk Arrays Eric J. Schwabe, Ian M. Sutherland, Northwestern [2:40] Scheduling Trees Using FIFO Queues: A Control-Memory Tradeoff Sandeep N. Bhatt, Fan R. K. Chung, Bellcore; Tom Leighton, MIT; Arnold L. Rosenberg U. Massachusetts, Amherst [3:00] Discussion %--------------------------------------------------------------------- [3:30] Break %--------------------------------------------------------------------- Session D [4:00] Studying Overheads in Massively Parallel MIN/MAX-Tree Evaluation Rainer Feldmann, Peter Mysliwietz, Burkhard Monien, U. Paderborn [4:20] List Ranking and List Scan on the CRAY C-90 Margaret Reid-Miller, CMU [4:40] Dynamic Parallel Tree Contraction John H. Reif, CMU and Duke; Stephen R. Tate, U. North Texas [5:00] Experiences with Parallel N-body Simulation Pangfeng Liu, DIMACS; Sandeep N. Bhatt, Bellcore [5:20] Discussion [5:50] Break [7:00] Round 5 of the International Computer Chess Championship [8:00] SPAA Business Meeting %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% TUESDAY, JUNE 28, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [7:45] Continental Breakfast Session E [8:30] Bandwidth-Based Lower Bounds on Slowdown for Efficient Emulations Between Fixed-Connection Networks Clyde P. Kruskal, U. Maryland; Kevin J. Rappoport, Pacific-Sierra Research [8:50] AT^2 Bounds for a Class of VLSI Problems and String Matching Micah Adler, John Byers, U.C. Berkeley [9:10] An $\Omega(\sqrt(\log\log n))$ Lower Bound for Routing in Optical Networks Leslie Ann Goldberg, Sandia; Mark Jerrum U. Edinburgh; Philip D. MacKenzie, U. Texas, Austin [9:30] Discussion %--------------------------------------------------------------------- [9:50] Break %--------------------------------------------------------------------- Session F [10:20] Programming DEC-Alpha Based Multiprocessors The Easy Way Hagit Attiya, Roy Friedman, Technion [10:40] Diffracting Trees Nir Shavit, Asaph Zemach Tel Aviv U. [11:00] On Testing Cache-Coherent Shared Memories Phillip B. Gibbons, AT&T Bell Labs, Ephraim Korach Ben-Gurion U. [11:20] Modeling Communication in Parallel Algorithms: A Fruitful Interaction between Theory and Systems? Jaswinder Pal Singh, Stanford; Edward Rothberg, Intel; Anoop Gupta, Stanford [11:40] Discussion %--------------------------------------------------------------------- [12:10] Lunch, including the presentation of awards for the International Computer Chess Championship %--------------------------------------------------------------------- Session G [1:40] Scheduling Parallelizable Tasks to Minimize Average Response Time John Turek, IBM, Yorktown; Walter Ludwig, U. Wisconsin, Madison; Joel Wolf, IBM, Yorktown; Lisa Fleischer, Cornell; Prasoon Tiwari, IBM, Yorktown; Jason Glasgow, Technion; Uwe Schweigelshohn, U. Dortmund; Philip S. Yu, IBM, Yorktown [2:00] Job Scheduling in Rings Perry Fizzano, Dartmouth; David Karger, Stanford; Clifford Stein, Dartmouth; Joel Wein, Polytechnic U. [2:20] An Analysis of Diffusive Load-Balancing Raghu Subramanian, Isaac D. Scherson, U.C. Irvine [2:40] Dynamic Load Balancing in Distributed Networks by Random Matchings Bhaskar Ghosh, Yale; S. Muthukrishnan, NYU [3:00] Discussion %--------------------------------------------------------------------- [3:30] Break %--------------------------------------------------------------------- [7:30] SPAA Conference Banquet Banquet Speaker: Monty Newborn, McGill University, speaking on Computer Chess %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% WEDNESDAY, JUNE 29, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [8:15] Continental Breakfast Session H [9:00] Efficient Low-Contention Parallel Algorithms Phillip B. Gibbons, Yossi Matias, AT&T Bell Labs; Vijaya Ramachandran, U. Texas, Austin [9:20] Constructive Deterministic PRAM Simulation on a Mesh-Connected Computer Andrea Pietracaprina, Brown; Geppino Pucci, U. Padova; Jop F. Sibeyn, MPI, Saarbrucken [9:40] An Optical Shared Memory Simulation Leslie Ann Goldberg, Sandia; Yossi Matias, AT&T Bell Labs; Satish Rao, NEC [10:00] Discussion %--------------------------------------------------------------------- [10:20] Break %--------------------------------------------------------------------- Session I [10:50] Construction of the Mesh and the Torus Tolerating a Large Number of Faults Hisao Tamaki, IBM, Yorktown [11:10] O(\log^2 n) Time Efficient Parallel Factorization of Dense, Sparse Separable, and Banded Matrices John H. Reif, CMU and Duke [11:30] How Much Can We Speedup Gaussian Elimination with Pivoting? M. Leoncini, U. Pisa [11:50] Discussion %--------------------------------------------------------------------- [12:10] Lunch %--------------------------------------------------------------------- Session J [1:40] Efficient Algorithms for All-to-All Communications in Multi-Port Message-Passing Systems Jehoshua Bruck, Ching-Tien Ho, IBM, Almaden; Shlomo Kipnis, IBM, Haifa; Derrick Weathersby, U. Washington, Seattle [2:00] An Architecture for Optimal All-to-All Personalized Communication Susan Hinrichs, Corey Kosak, Dave O'Hallaron, Thomas M. Stricker, Riichiro Take, CMU [2:20] Communication-Efficient Matrix Multiplication on Hypercubes Himanshu Gupta, P. Sadayappan, Ohio State [2:40] A Model for Multi-Grained Parallelism John E. Savage, Brown [3:00] Discussion %--------------------------------------------------------------------- [3:30] Break %--------------------------------------------------------------------- Session K [4:00] Increasing Network Bandwidth on Meshes Jerry Stamatopoulos, Jon A. Solworth, U. Illinois, Chicago [4:20] Bounds on the Greedy Routing Algorithm for Array Networks Michael Mitzenmacher, U.C. Berkeley [4:40] Minimal Adaptive Routing on the Mesh with Bounded Queue Size Donald D. Chinn, U. Washington, Seattle; Tom Leighton, MIT; Martin Tompa, U. Washington, Seattle [5:00] Segment Router: A Novel Router Design for Parallel Computers S. Konstantinidou, IBM, Yorktown [5:20] Discussion %--------------------------------------------------------------------- [5:50] Adjourn %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ACM's 24th International Computer Chess Championship All SPAA attendees are invited to attend ACM's 24th International Computer Chess Championship, which will be held as a special event Saturday through Monday, June 25--27, 1994. The five-round Swiss-style event will be played at a rate of 40 moves in the first two hours and 20 moves every hour thereafter. Two rounds are scheduled on Saturday, two on Sunday, and the final round will take place Monday evening. The field will be limited to twelve teams. With the level of play of the top programs at the grandmaster level, the event promises to be one more important milestone in the history of the rapid progress of chess programming. Several of the participants are expected to use large multiprocessing systems, while others will use high-speed personal computers. For more information or to enter, contact Monty Newborn, School of Computer Science, McGill University, 3480 University Street, Montreal, Quebec, Canada H3A 2A7; Phone: 514-398-7079; Internet: newborn@cs.mcgill.ca. Entries close on June 2, 1994. General Information Location: All conference events will take place at the oceanfront Grand Hotel in Cape May, New Jersey. Cape May is one of the oldest seashore resorts in America and is situated between the Atlantic Ocean and Delaware Bay. It is a quaint village that features over 600 fully restored Victorian homes. Activities include trolley and walking tours of Cape May, whale watching and other boat tours, deep sea fishing, birdwatching, golf, tennis, surfing, and swimming. There are also numerous parks nearby, including Leamings Run Botanical Gardens and Cape May Point State Park, which features a lighthouse, nature trails and a nature center. Other nearby attractions include Atlantic City with numerous evening shows as well as gambling, the amusement parks on the boardwalk in the Wildwoods which have more rides than Disneyland, and Cold Spring Village, a recreated historic village, life and crafts of yesterday. Information on all these activities will be included in your registration packets. Climate: June temperatures are pleasant, ranging as high as 85 F. (about 30 C.) during the day down to as low as 60 F. (about 15 C.) at night. Registration: A registration desk will be open from 7:00 p.m. until 9:00 p.m. on Sunday, July 21, and during the day on Monday through Wednesday. Student Support: Some travel money may be available for students wishing to attend SPAA'94. Priority will be given to speakers and authors with insufficient funds. If interested, please contact Bruce Maggs via the Internet at bmm@cs.cmu.edu. Reception and Banquet: There will be a reception for all registrants from 7:00 p.m. until 10:00 p.m. on Sunday evening at the Grand Hotel. The conference banquet will be at 7:30 p.m. on Tuesday evening. Extra banquet tickets will be available at the conference for $35 each. Business Meeting: The annual SPAA business meeting will be held at 8:00 p.m. on Monday evening. All registrants are encouraged to attend. A variety of subjects will be discussed, including the location of future SPAA's and program committee policy. A special discussion will be held this year on how the program committee should evaluate empirical research. Further Information: For further information, contact the local arrangement chairs Yuh-Dauh Lyuu or Satish Rao, NEC Research Institute, 4 Independence Way, Princeton, NJ 08540; Phone: 609-951-2714; Fax: 609-951-2496; Internet: spaa94@research.nj.nec.com. Transportation If your transportation requirements are not addressed in the following text, please contact the local arrangement chairs via the Internet at spaa94@research.nj.nec.com. By Air: The Grand Hotel is located at Beach Avenue and Philadelphia Avenue in Cape May, New Jersey. Cape May is located about 45 minutes (by car) from the Atlantic City Airport, two hours from the Philadelphia Airport, and three hours from Newark Airport. Airlines that fly to the Atlantic City Airport (609-645-7895) include Continental Express, Northwest, USAir, and Spirit. Avis is offering a discount on weekly rates for rental cars to attendees of the SPAA conference. Rates start at $140 when originating at Atlantic City or Philadelphia Airport and at $180 when originating at Newark. If you are interested, please call 800-331-1600, and mention ``the SPAA Conference'' and the conference number Y524004. SPAA'94 will provide free shuttle service between Philadelphia Airport and Cape May with the following tentative schedule: Philadelphia Airport to Grand Hotel} June 25, 4:00 p.m. June 25, 8:00 p.m. June 26, 4:00 p.m. June 26, 8:00 p.m. Grand Hotel to Philadelphia Airport June 29, 6:00 p.m. June 30, 8:00 a.m. June 30, 11:00 a.m. SPAA'94 may also be able to provide free shuttle service between Atlantic City Airport and Cape May. If you are interested in shuttle service from either airport, please indicate on the registration form when and where your flights will arrive and depart. By Train: Amtrak (800-872-7245) serves Atlantic City, and New Jersey Transit (201-762-5100) provides busses between Atlantic City and Cape May. The train station is across the street from the bus terminal. By Bus: New Jersey Transit buses depart from Atlantic City Bus Terminal (201-762-5100), from Philadelphia (215-569-3752), and the from the Port Authority Bus Terminal (201-460-8444) in New York City. By Car: Cape May is located at the southernmost tip of the New Jersey shore. Using the Garden State Parkway (toll road), travel south to the end of the Parkway. Continue straight through a traffic light over a large concrete overpass and then over a small canal bridge into the city of Cape May. You will be on Lafayette Street. Continue to the first traffic light, and turn left onto Madison Avenue. Once you reach the ocean, take a left onto Beach Drive. The hotel is on the left at Philadelphia Avenue. To reach the Garden State Parkway from Philadelphia Airport, travel north on Interstate 95. Take Interstate 76 East across the Walt Whitman Bridge. After crossing the bridge, stay in the left lane. You will be on the North-South Freeway (Route 42). Follow 8 to 11 miles to the Atlantic City Expressway East (toll road) to the Garden State Parkway South. To reach the Garden State Parkway from the Delaware Memorial Bridge, take Route 40 East to Route 55 South to Route 47 South to the Garden State Parkway South. To get to Cape May from the Cape May--Lewes Ferry (609-886-9699), follow Route 109 and signs Cape May/Wildwood, and then, to the concrete overpass and canal bridge into the city of Cape May. You will be on Lafayette Street. Continue to the first traffic light, and turn left onto Madison Avenue. Once you reach the ocean, take a left onto Beach Drive. The hotel is on the left at Philadelphia Avenue. SPAA'94 Organization Conference Chair Lawrence Snyder, U. Washington, Seattle Treasurer Bruce Maggs, CMU Local Arrangements Satish Rao, Yuh-Dauh Lyuu, NEC Research Institute Program Committee Gianfranco Bilardi, U. Padova Tom Blank, MasPar Guy Blelloch, CMU David Culler, U.C. Berkeley Robert Cypher, IBM, Almaden Torben Hagerup, Max Planck Institute Charles E. Leiserson (Chair), MIT Trevor N. Mudge, U. Michigan, Ann Arbor Cynthia A. Phillips, Sandia National Laboratories Steve Scott, Cray Research C. Gregory Plaxton, U. Texas, Austin Rob Schreiber, RIACS Corporate Affiliates DIMACS Center for Discrete Mathematics and Theoretical Computer Science New Brunswick, NJ Elsevier Science Publishers Amsterdam, The Netherlands NEC Research Institute Princeton, NJ Plenum Publishing Corporation New York, NY PWS Publishing Company Belmont, CA Newsgroups: comp.parallel,comp.architecture,comp.theory Subject: 6th Annual ACM Symposium on Parallel Algorithms and Architectures Distribution: world Organization: Computer Science Department, Oregon State University Keywords: ADVANCED PROGRAM 6th Annual ACM Symposium on Parallel Algorithms and Architectures Advanced Program __________________________________________________________________________ SPAA'94 6th Annual ACM Symposium on Parallel Algorithms and Architectures Cape May, New Jersey June 26 -- 29, 1994 ACM's 24th International Computer Chess Championship June 25 -- 27, 1994 Sponsored by ACM SIGACT and ACM SIGArch In Cooperation with EATCS Registration for SPAA'94 The registration fees for SPAA'94 are listed below. To qualify for the early registration fee, your registration application must be postmarked by **Friday, May 20**. Refund requests will be honored until June 15. The nonstudent registration fee includes the Sunday night reception, the Monday night business meeting, the Tuesday night banquet, coffee breaks and lunches, and a copy of the proceedings. The student fee includes all of the above except the banquet. Please fill out the form below and send it, along with a check or money order made payable to "SPAA'94," to: SPAA'94 c/o Yuh-dauh Lyuu, Satish Rao NEC Research Institute 4 Independence Way Princeton, NJ 08540 Name _________________________________________________________ Affiliation ________________________________________________________ Street Address ________________________________________________________ City ____________________ State ___________________________ ZIP or Postal # ___________________ Country _____________________________ Internet address _____________________________ Phone _____________________________ Please circle one, and fill in your membership number, if appropriate: Category Fee After 5/20 ACM, SIGACT or SIGArch member 285 335 EATCS member 285 335 Author or Program Committee member 285 335 Student 130 150 Other 345 395 Check your dietary preference: Vegetarian __________________ No Restriction ___________ If you are interested in a shuttle from Philadelphia Airport or Atlantic City Airport, please see information later in this brochure under Transportation, and indicate time and location of flights below or e-mail spaa94@research.nj.nec.com. -------------------------- Arriving flight __________________________________________________________ Departing flight ________________________________________________________ Hotel Reservations The conference will be held at the Grand Hotel in Cape May. The rates for SPAA'94 are posted below and apply from Friday, June 24 through Thursday, June 30. Checkin time is 2 p.m. and checkout is 11 a.m. Arrivals earlier than 2 p.m. will be accommodated as rooms become available. Please advise the hotel of late arrival. Reservations should be made by ***Friday, May 20***. Reservations made after that will be accepted on a rate and space availability basis. To make your reservations by phone, call the Grand Hotel at 609-884-5611 or 800-257-8550 and refer to SPAA'94. To make reservations by mail, fill out the form below and send it to the address below. A deposit in the form of a check or money order for one night's stay or credit card information must be included. When filling out the form, make sure that you list your name exactly as it appears on your check or credit card. The following credit cards are accepted: American Express, Diners Club, Visa, and Mastercard. If you cancel and notify the hotel at least two weeks before your specified arrival, 75 percent of your deposit will be refunded. For babysitting service request, please indicate ages of the children and the times on the form below. The Grand Hotel ATTN: SPAA'94 Reservations P.O. Box 496 Cape May, New Jersey 08204 Fax: 609-898-0341 Single $100 ____________ Double (1 bed) $100 ____________________ Double (2 beds) $100 ____________ Triple $110 ____________________ Quad $120 _____________ Check-in date __________________ Check-out date ____________________ Name ___________________________________________________ Address ___________________________________________________ Phone ___________________________________________________ Sharing room with __________________________________________________ Babysitting requests (times/child's age) ___________________________ If paying for deposit by credit card, please complete: Credit Card Number ___________________________ Credit Card Type _______________ Expiration Date _____________ I authorize The Grand Hotel of Cape May to charge the above account an amount equal to one night's stay as deposit. Signature ______________________________ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% SATURDAY, JUNE 25, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [11:00] Round 1 of the International Computer Chess Championship [7:00] Round 2 of the International Computer Chess Championship %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% SUNDAY, JUNE 26, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [9:30] Round 3 of the International Computer Chess Championship [4:00] Technical Session on Recent Developments in Computer Chess [5:00] Break [7:00] Round 4 of the International Computer Chess Championship [7:00] Conference reception for all SPAA attendees %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% MONDAY, JUNE 27, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [8:00] Continental Breakfast [8:45] Welcoming Remarks by SPAA'94 Organizers Session A [9:00] An Optimal Randomized Logarithmic Time Connectivity Algorithm for the EREW PRAM Shay Halperin, Uri Zwick, Tel Aviv U. [9:20] A Linear-Work Parallel Algorithm for Finding a Minimum Spanning Tree Richard Cole, NYU; Philip N. Klein, Brown; Robert E. Tarjan; Princeton and NEC [9:40] A Comparison of Parallel Algorithms for Connected Components John Greiner, CMU [10:00] Discussion %--------------------------------------------------------------------- [10:20] Break %--------------------------------------------------------------------- Session B [10:50] Improved Bounds for Routing and Sorting on Multi-Dimensional Meshes Torsten Suel, U. Texas, Austin [11:10] 2d-Bubblesorting in O(\sqrt(N \lg N)) Time in the Average Case Doug Ierardi, USC [11:30] Parallel Sorting by Overpartitioning Hui Li, Kenneth C. Sevcik, Toronto [11:50] Discussion %--------------------------------------------------------------------- [12:10] Lunch %--------------------------------------------------------------------- Session C [1:40] Efficient Compilation of High-Level Data Parallel Algorithms Dan Suciu, Val Tannen, U. Pennsylvania [2:00] SIMD Instruction Cache Todd E. Rockoff, Flinders U. [2:20] Improved Parity-Declustered Layouts for Disk Arrays Eric J. Schwabe, Ian M. Sutherland, Northwestern [2:40] Scheduling Trees Using FIFO Queues: A Control-Memory Tradeoff Sandeep N. Bhatt, Fan R. K. Chung, Bellcore; Tom Leighton, MIT; Arnold L. Rosenberg U. Massachusetts, Amherst [3:00] Discussion %--------------------------------------------------------------------- [3:30] Break %--------------------------------------------------------------------- Session D [4:00] Studying Overheads in Massively Parallel MIN/MAX-Tree Evaluation Rainer Feldmann, Peter Mysliwietz, Burkhard Monien, U. Paderborn [4:20] List Ranking and List Scan on the CRAY C-90 Margaret Reid-Miller, CMU [4:40] Dynamic Parallel Tree Contraction John H. Reif, CMU and Duke; Stephen R. Tate, U. North Texas [5:00] Experiences with Parallel N-body Simulation Pangfeng Liu, DIMACS; Sandeep N. Bhatt, Bellcore [5:20] Discussion [5:50] Break [7:00] Round 5 of the International Computer Chess Championship [8:00] SPAA Business Meeting %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% TUESDAY, JUNE 28, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [7:45] Continental Breakfast Session E [8:30] Bandwidth-Based Lower Bounds on Slowdown for Efficient Emulations Between Fixed-Connection Networks Clyde P. Kruskal, U. Maryland; Kevin J. Rappoport, Pacific-Sierra Research [8:50] AT^2 Bounds for a Class of VLSI Problems and String Matching Micah Adler, John Byers, U.C. Berkeley [9:10] An $\Omega(\sqrt(\log\log n))$ Lower Bound for Routing in Optical Networks Leslie Ann Goldberg, Sandia; Mark Jerrum U. Edinburgh; Philip D. MacKenzie, U. Texas, Austin [9:30] Discussion %--------------------------------------------------------------------- [9:50] Break %--------------------------------------------------------------------- Session F [10:20] Programming DEC-Alpha Based Multiprocessors The Easy Way Hagit Attiya, Roy Friedman, Technion [10:40] Diffracting Trees Nir Shavit, Asaph Zemach Tel Aviv U. [11:00] On Testing Cache-Coherent Shared Memories Phillip B. Gibbons, AT&T Bell Labs, Ephraim Korach Ben-Gurion U. [11:20] Modeling Communication in Parallel Algorithms: A Fruitful Interaction between Theory and Systems? Jaswinder Pal Singh, Stanford; Edward Rothberg, Intel; Anoop Gupta, Stanford [11:40] Discussion %--------------------------------------------------------------------- [12:10] Lunch, including the presentation of awards for the International Computer Chess Championship %--------------------------------------------------------------------- Session G [1:40] Scheduling Parallelizable Tasks to Minimize Average Response Time John Turek, IBM, Yorktown; Walter Ludwig, U. Wisconsin, Madison; Joel Wolf, IBM, Yorktown; Lisa Fleischer, Cornell; Prasoon Tiwari, IBM, Yorktown; Jason Glasgow, Technion; Uwe Schweigelshohn, U. Dortmund; Philip S. Yu, IBM, Yorktown [2:00] Job Scheduling in Rings Perry Fizzano, Dartmouth; David Karger, Stanford; Clifford Stein, Dartmouth; Joel Wein, Polytechnic U. [2:20] An Analysis of Diffusive Load-Balancing Raghu Subramanian, Isaac D. Scherson, U.C. Irvine [2:40] Dynamic Load Balancing in Distributed Networks by Random Matchings Bhaskar Ghosh, Yale; S. Muthukrishnan, NYU [3:00] Discussion %--------------------------------------------------------------------- [3:30] Break %--------------------------------------------------------------------- [7:30] SPAA Conference Banquet Banquet Speaker: Monty Newborn, McGill University, speaking on Computer Chess %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% WEDNESDAY, JUNE 29, 1994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [8:15] Continental Breakfast Session H [9:00] Efficient Low-Contention Parallel Algorithms Phillip B. Gibbons, Yossi Matias, AT&T Bell Labs; Vijaya Ramachandran, U. Texas, Austin [9:20] Constructive Deterministic PRAM Simulation on a Mesh-Connected Computer Andrea Pietracaprina, Brown; Geppino Pucci, U. Padova; Jop F. Sibeyn, MPI, Saarbrucken [9:40] An Optical Shared Memory Simulation Leslie Ann Goldberg, Sandia; Yossi Matias, AT&T Bell Labs; Satish Rao, NEC [10:00] Discussion %--------------------------------------------------------------------- [10:20] Break %--------------------------------------------------------------------- Session I [10:50] Construction of the Mesh and the Torus Tolerating a Large Number of Faults Hisao Tamaki, IBM, Yorktown [11:10] O(\log^2 n) Time Efficient Parallel Factorization of Dense, Sparse Separable, and Banded Matrices John H. Reif, CMU and Duke [11:30] How Much Can We Speedup Gaussian Elimination with Pivoting? M. Leoncini, U. Pisa [11:50] Discussion %--------------------------------------------------------------------- [12:10] Lunch %--------------------------------------------------------------------- Session J [1:40] Efficient Algorithms for All-to-All Communications in Multi-Port Message-Passing Systems Jehoshua Bruck, Ching-Tien Ho, IBM, Almaden; Shlomo Kipnis, IBM, Haifa; Derrick Weathersby, U. Washington, Seattle [2:00] An Architecture for Optimal All-to-All Personalized Communication Susan Hinrichs, Corey Kosak, Dave O'Hallaron, Thomas M. Stricker, Riichiro Take, CMU [2:20] Communication-Efficient Matrix Multiplication on Hypercubes Himanshu Gupta, P. Sadayappan, Ohio State [2:40] A Model for Multi-Grained Parallelism John E. Savage, Brown [3:00] Discussion %--------------------------------------------------------------------- [3:30] Break %--------------------------------------------------------------------- Session K [4:00] Increasing Network Bandwidth on Meshes Jerry Stamatopoulos, Jon A. Solworth, U. Illinois, Chicago [4:20] Bounds on the Greedy Routing Algorithm for Array Networks Michael Mitzenmacher, U.C. Berkeley [4:40] Minimal Adaptive Routing on the Mesh with Bounded Queue Size Donald D. Chinn, U. Washington, Seattle; Tom Leighton, MIT; Martin Tompa, U. Washington, Seattle [5:00] Segment Router: A Novel Router Design for Parallel Computers S. Konstantinidou, IBM, Yorktown [5:20] Discussion %--------------------------------------------------------------------- [5:50] Adjourn %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ACM's 24th International Computer Chess Championship All SPAA attendees are invited to attend ACM's 24th International Computer Chess Championship, which will be held as a special event Saturday through Monday, June 25--27, 1994. The five-round Swiss-style event will be played at a rate of 40 moves in the first two hours and 20 moves every hour thereafter. Two rounds are scheduled on Saturday, two on Sunday, and the final round will take place Monday evening. The field will be limited to twelve teams. With the level of play of the top programs at the grandmaster level, the event promises to be one more important milestone in the history of the rapid progress of chess programming. Several of the participants are expected to use large multiprocessing systems, while others will use high-speed personal computers. For more information or to enter, contact Monty Newborn, School of Computer Science, McGill University, 3480 University Street, Montreal, Quebec, Canada H3A 2A7; Phone: 514-398-7079; Internet: newborn@cs.mcgill.ca. Entries close on June 2, 1994. General Information Location: All conference events will take place at the oceanfront Grand Hotel in Cape May, New Jersey. Cape May is one of the oldest seashore resorts in America and is situated between the Atlantic Ocean and Delaware Bay. It is a quaint village that features over 600 fully restored Victorian homes. Activities include trolley and walking tours of Cape May, whale watching and other boat tours, deep sea fishing, birdwatching, golf, tennis, surfing, and swimming. There are also numerous parks nearby, including Leamings Run Botanical Gardens and Cape May Point State Park, which features a lighthouse, nature trails and a nature center. Other nearby attractions include Atlantic City with numerous evening shows as well as gambling, the amusement parks on the boardwalk in the Wildwoods which have more rides than Disneyland, and Cold Spring Village, a recreated historic village, life and crafts of yesterday. Information on all these activities will be included in your registration packets. Climate: June temperatures are pleasant, ranging as high as 85 F. (about 30 C.) during the day down to as low as 60 F. (about 15 C.) at night. Registration: A registration desk will be open from 7:00 p.m. until 9:00 p.m. on Sunday, July 21, and during the day on Monday through Wednesday. Student Support: Some travel money may be available for students wishing to attend SPAA'94. Priority will be given to speakers and authors with insufficient funds. If interested, please contact Bruce Maggs via the Internet at bmm@cs.cmu.edu. Reception and Banquet: There will be a reception for all registrants from 7:00 p.m. until 10:00 p.m. on Sunday evening at the Grand Hotel. The conference banquet will be at 7:30 p.m. on Tuesday evening. Extra banquet tickets will be available at the conference for $35 each. Business Meeting: The annual SPAA business meeting will be held at 8:00 p.m. on Monday evening. All registrants are encouraged to attend. A variety of subjects will be discussed, including the location of future SPAA's and program committee policy. A special discussion will be held this year on how the program committee should evaluate empirical research. Further Information: For further information, contact the local arrangement chairs Yuh-Dauh Lyuu or Satish Rao, NEC Research Institute, 4 Independence Way, Princeton, NJ 08540; Phone: 609-951-2714; Fax: 609-951-2496; Internet: spaa94@research.nj.nec.com. Transportation If your transportation requirements are not addressed in the following text, please contact the local arrangement chairs via the Internet at spaa94@research.nj.nec.com. By Air: The Grand Hotel is located at Beach Avenue and Philadelphia Avenue in Cape May, New Jersey. Cape May is located about 45 minutes (by car) from the Atlantic City Airport, two hours from the Philadelphia Airport, and three hours from Newark Airport. Airlines that fly to the Atlantic City Airport (609-645-7895) include Continental Express, Northwest, USAir, and Spirit. Avis is offering a discount on weekly rates for rental cars to attendees of the SPAA conference. Rates start at $140 when originating at Atlantic City or Philadelphia Airport and at $180 when originating at Newark. If you are interested, please call 800-331-1600, and mention ``the SPAA Conference'' and the conference number Y524004. SPAA'94 will provide free shuttle service between Philadelphia Airport and Cape May with the following tentative schedule: Philadelphia Airport to Grand Hotel} June 25, 4:00 p.m. June 25, 8:00 p.m. June 26, 4:00 p.m. June 26, 8:00 p.m. Grand Hotel to Philadelphia Airport June 29, 6:00 p.m. June 30, 8:00 a.m. June 30, 11:00 a.m. SPAA'94 may also be able to provide free shuttle service between Atlantic City Airport and Cape May. If you are interested in shuttle service from either airport, please indicate on the registration form when and where your flights will arrive and depart. By Train: Amtrak (800-872-7245) serves Atlantic City, and New Jersey Transit (201-762-5100) provides busses between Atlantic City and Cape May. The train station is across the street from the bus terminal. By Bus: New Jersey Transit buses depart from Atlantic City Bus Terminal (201-762-5100), from Philadelphia (215-569-3752), and the from the Port Authority Bus Terminal (201-460-8444) in New York City. By Car: Cape May is located at the southernmost tip of the New Jersey shore. Using the Garden State Parkway (toll road), travel south to the end of the Parkway. Continue straight through a traffic light over a large concrete overpass and then over a small canal bridge into the city of Cape May. You will be on Lafayette Street. Continue to the first traffic light, and turn left onto Madison Avenue. Once you reach the ocean, take a left onto Beach Drive. The hotel is on the left at Philadelphia Avenue. To reach the Garden State Parkway from Philadelphia Airport, travel north on Interstate 95. Take Interstate 76 East across the Walt Whitman Bridge. After crossing the bridge, stay in the left lane. You will be on the North-South Freeway (Route 42). Follow 8 to 11 miles to the Atlantic City Expressway East (toll road) to the Garden State Parkway South. To reach the Garden State Parkway from the Delaware Memorial Bridge, take Route 40 East to Route 55 South to Route 47 South to the Garden State Parkway South. To get to Cape May from the Cape May--Lewes Ferry (609-886-9699), follow Route 109 and signs Cape May/Wildwood, and then, to the concrete overpass and canal bridge into the city of Cape May. You will be on Lafayette Street. Continue to the first traffic light, and turn left onto Madison Avenue. Once you reach the ocean, take a left onto Beach Drive. The hotel is on the left at Philadelphia Avenue. SPAA'94 Organization Conference Chair Lawrence Snyder, U. Washington, Seattle Treasurer Bruce Maggs, CMU Local Arrangements Satish Rao, Yuh-Dauh Lyuu, NEC Research Institute Program Committee Gianfranco Bilardi, U. Padova Tom Blank, MasPar Guy Blelloch, CMU David Culler, U.C. Berkeley Robert Cypher, IBM, Almaden Torben Hagerup, Max Planck Institute Charles E. Leiserson (Chair), MIT Trevor N. Mudge, U. Michigan, Ann Arbor Cynthia A. Phillips, Sandia National Laboratories Steve Scott, Cray Research C. Gregory Plaxton, U. Texas, Austin Rob Schreiber, RIACS Corporate Affiliates DIMACS Center for Discrete Mathematics and Theoretical Computer Science New Brunswick, NJ Elsevier Science Publishers Amsterdam, The Netherlands NEC Research Institute Princeton, NJ Plenum Publishing Corporation New York, NY PWS Publishing Company Belmont, CA