ftl%math.mit.edu@VM1.NoDak.EDU (Tom Leighton) (05/03/91)
[I picked this off comp.theory. There is increasing traffic on comp.theory
of interest to readers of this group. If you are not a subscriber and
you do not have a news feed, contact
<THEORY-A@VM1.NoDak.EDU> or
Tom Leighton <ftl@BOURBAKI.MIT.EDU>
---steve]
\documentstyle[twocolumn]{article}
\textwidth=7.7in
\columnsep=.875in
\textheight=8.5in
\oddsidemargin-.75in
\evensidemargin0pt
\def\subheading#1{\noindent {\bf#1}\smallskip}
\setbox0=\hbox{\bf 10:20}
\labelwidth=\wd0
\leftmargini\labelwidth
\advance\leftmargini by .5em
\makeatletter
\def\description{\ifnum \@itemdepth >3 \@toodeep\else \advance\@itemdepth \@ne
\edef\@itemitem{labelitem\romannumeral\the\@itemdepth}%
\list{\csname\@itemitem\endcsname}%
{\parsep0pt\def\makelabel##1{\bf##1\hss}}\fi}
\let\enddescription =\endlist
\makeatother
\tabcolsep 3pt
\def\brule#1{\vrule width#1 height 0.4pt depth 0.0pt\relax}
\def\heading#1{\begin{center}\Large\bf#1\end{center}}
\pagestyle{empty}
\begin{document}
\vspace*{1in}
{\Huge \it SPAA '91}
\vspace*{.75in}
\heading{3rd Annual ACM Symposium\\
\vspace{.09in}
on Parallel Algorithms\\
\vspace{.09in}
and Architectures}
\vspace{2.25in}
\heading{July 21 - 24, 1991\\
\vspace{.09in}
Hilton Head, South Carolina}
\vspace{.75in}
\begin{center}
Sponsored by\\
ACM SIGACT and ACM SIGArch
\smallskip
In Cooperation with\\
IEEE and EATCS
\end{center}
\newpage
\heading{Registration for SPAA '91}
The registration fees for SPAA '91 are listed below.
To qualify for the early registration fee, your registration application
must be postmarked by {\bf Friday, June 14}. Refund requests will be honored
until July 1.
The non-student 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 '91,'' to:
\begin{center}
Bill Aiello/ATTN: SPAA '91\\
MRE-2P363\\
Bellcore\\
445 South Street\\
Morristown, NJ 07960
\end{center}
\begingroup
\parindent=0pt
\begingroup
\baselineskip=14pt
Name\hrulefill
Affiliation\hrulefill
Street Address\hrulefill
City\hrulefill State\hrulefill
ZIP or Country \& Postal \#\hrulefill
Email\hrulefill Phone\hrulefill
\bigskip
Please circle one and fill in your membership number if appropriate:
\#\hrulefill
\medskip
\begin{tabular}{@{}lcc}
\bf Category & \bf Fee & \bf After\\
& & \bf 6/14 \\
ACM, SIGACT or SIGArch member & 235 & 285 \\
IEEE or EATCS member & 235 & 285 \\
Author or Program Committee member & 235 & 285 \\
Student & 60 & 95 \\
Other & 285 & 335
\end{tabular}
\bigskip
Check your dietary preference.
Kosher\hrulefill Vegetarian\hrulefill No Restriction\hrulefill
\medskip
\endgroup
Indicate the number of reservations for Sunday, July 21
you would like for the activities below. Information
about these activities is included in General Information.
\medskip
Golf\hrulefill Volleyball\hrulefill Nature Hike\hrulefill
\smallskip
Tennis: People\brule{.5in}Hours\brule{.5in}
\endgroup
\newpage
\heading{Hotel Reservations}
The conference will be held at Marriott's Hilton Head Resort. The
rates for SPAA '91 are posted below and apply from Friday, July 19 through
Sunday, July 28. Checkin time is 4pm and checkout is 12 noon. Arrivals
earlier than 4 pm will be accomodated as rooms become available.
Please advise the hotel of late arrival.
Reservations should be made by {\bf Friday, June 21}.
Reservations made after that will be accepted on a rate and space
availability basis. Refer to SPAA '91 when making your reservations
to obtain the rates listed.
To make your reservations by phone, call Marriott's Hilton
Head Resort at (803) 842-2400 or (800) 334-1881.
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, Mastercard,
and Carte Blanche. Deposits will be refunded if the hotel is notified
at least 48 hours before your specified arrival.
\begin{center}
Marriott's Hilton Head Resort\\
ATTN: SPAA '91 Reservations\\
130 Shipyard Drive, Shipyard Plantation\\
Hilton Head Island, SC 29928\\
\end{center}
\begingroup
\parindent=0pt
\begingroup
\baselineskip=14pt
Please check one:
\medskip
Single \$105\hrulefill Double (1 bed) \$105\hrulefill
\smallskip
Double (2 beds) \$105\hrulefill Triple \$125\hrulefill Quad
\$145\hrulefill
\medskip
Please fill out:
\medskip
Name\hrulefill
\smallskip
Address\hrulefill
\smallskip
\brule{1.65in} Phone\hrulefill
\smallskip
Sharing room with\hrulefill
\medskip
If paying for deposit by credit card please complete:
\smallskip
Credit Card Number\hrulefill
\smallskip
Expiration Date\hrulefill
\medskip
I authorize Marriott's Hilton Head Resort to charge the
above account for the amount equal to one night's stay as deposit.
\smallskip
Signature\hrulefill
\endgroup
\newpage
\begin{center}
\subheading{MONDAY, JULY 22, 1991}
\end{center}
\begin{description}
\item[9:00]{\bf Invited Speaker}
Malvin Kalos, {\it Director, Cornell Theory Center}
{\it``Architectural and Theoretical Implications of Monte
Carlo Calculations''}
\item[9:55]{\bf Break}
\end{description}
\begin{center}
\subheading{Session 1}
\end{center}
\begin{description}
\item[10:20] {\it A Comparison of Sorting Algorithms for the Connection
Machine CM-2}
G.E. Blelloch, {\it CMU;} C.E. Leiserson, {\it MIT;} B.M. Maggs, {\it NEC
Research Institute;} C.G. Plaxton, {\it U. Texas;} S.J. Smith,
{\it Thinking Machines;} M. Zagha, {\it CMU}
\item[10:45] {\it Randomized Sorting and Selection on Mesh-Connected
Processor Arrays}
C. Kaklamanis, {\it Harvard;} D. Krizanc, L. Nara\-yanan,
{\it U. Rochester;} T. Tsantilas, {\it Columbia}
\item[11:10] {\it Large-Scale Sorting in Parallel Memories}
M.H. Nodine and J.S. Vitter, {\it Brown}
\item[11:35] {\it Optimal Speedup for Backtrack Search on a Butterfly
Network}
A. Ranade, {\it Berkeley}
\end{description}
\begin{description}
\item[12:00]{\bf Lunch}
\end{description}
\begin{center}
\subheading{Session 2}
\end{center}
\begin{description}
\item[1:30] {\it Fast and Reliable Parallel Hashing}
H. Bast, {\it U. Saarlands;} T. Hagerup, {\it Max-Planck-Institut}
\item[1:55] {\it Tight Bounds for the Chaining Problem}
S. Chaudhuri, {\it Rutgers}
\item [2:20] {\it Parallel Construction of Trees with Optimal
Weighted Path Length}
L.L. Larmore and T.M. Przytycka, {\it U. California/Riverside}
\item[2:45] {\it More Time-Work Tradeoffs for Parallel Graph
Algorithms}
T.H. Spencer, {\it RPI}
\end{description}
\begin{description}
\item[3:10]{\bf Break}
\end{description}
\newpage
\begin{center}
\subheading{Session 3}
\end{center}
\begin{description}
\item[3:45] {\it An Overview of Supertoroidal Networks}
R.N. Draper, {\it Supercomputing Research Center}
\item[4:10] {\it Architectural Primitives for a Scalable Shared Memory
Multiprocessor}
J. Lee and U. Ramachandran, {\it Georgia Institute of Technology}
\item[4:35] {\it Architectural Mechanisms to Support Three-Dimensional
Lattice Gas Simulations}
F.F. Lee and M.J. Flynn, {\it Stanford}
\end{description}
\begin{description}
\item[5:00]{\bf Break}
\end{description}
\begin{description}
\item[5:30]{\bf Open Problem Session}
\item[9:00]{\bf Business Meeting}
\end{description}
\begin{center}
\subheading{TUESDAY, JULY 23, 1991}
\end{center}
\begin{description}
\item[9:00]{\bf Invited Speaker}
Burton Smith, {\it Chairman and Chief Scientist, Tera Computer
Company}
{\it ``A Massively Parallel Shared Memory Computer''}
\item[9:55]{\bf Break}
\end{description}
\begin{center}
\subheading{Session 4}
\end{center}
\begin{description}
\item[10:20] {\it Coding Theory, Hypercube Embeddings, and Fault
Tolerance}
B. Aiello, {\it Bellcore;} T. Leighton, {\it MIT}
\item[10:45] {\it Embedding de Bruijn and Shuffle-Exchange Graphs in
Five Pages}
B. Obreni\'{c}, {\it U. Massachusetts}
\item[11:10] {\it Simulating Binary Trees on X-Trees}
B. Monien, {\it U. Paderborn}
\item[11:35]{\it An Approach to Emulating Separable Graphs}
B. Obreni\'{c}, {\it U. Massachusetts}
\end{description}
\begin{description}
\item[12:00]{\bf Lunch}
\end{description}
\begin{center}
\subheading{Session 5}
\end{center}
\begin{description}
\item[1:30]{\it Constructing Arrangements Optimally in Parallel}
M.T. Goodrich, {\it Johns Hopkins University}
\item[1:55]{\it Processor Efficient Parallel Solution of Linear Systems over an
Abstract Field}
E. Kaltofen, {\it U. Toronto and RPI;} V. Pan, {\it SUNY/Albany}
\item[2:20]{\it In-Place Techniques for Parallel Convex Hull
Algorithms}
M. Ghouse and M. Goodrich, {\it Johns Hopkins University}
\item[2:45]{\it Multisearch Techniques for Implementing Data Structures on a
Mesh-Connected Computer}
M.J. Atallah, {\it Purdue;} F. Dehne, {\it Carleton;}
R. Miller, {\it SUNY/Buffalo;} A. Rau-Chaplin, {\it Carleton;} J-J. Tsay,
{\it National Chung Cheng University}
\end{description}
\begin{description}
\item[3:10]{\bf Break}
\end{description}
\begin{center}
\subheading{Session 6}
\end{center}
\begin{description}
\item[3:45]{\it Generalized Multiprocessor Scheduling Using Optimal
Control}
G.N. Srinivasa Prasanna and B.R. Musicus, {\it MIT}
\item[4:10]{\it Lock-Free Garbage Collection for Multiprocessors}
M. Herlihy, {\it DEC;} J.E.B. Moss, {\it U. Massachusetts}
\item [4:35]{\it A Simple Load Balancing Scheme for Task Allocation in Parallel
Machines}
L. Rudolph, M. Slivkin, {\it Hebrew University;} E. Upfal, {\it Weizman
Institute and IBM Almaden}
\end{description}
\begin{description}
\item[5:00]{\bf Break}
\end{description}
\begin{description}
\item[7:30]{\bf Banquet}
\end{description}
\begin{center}
\subheading{WEDNESDAY, JULY 24, 1991}
\end{center}
\begin{description}
\item[9:00]{\bf Invited Speaker}
Franco P. Preparata, {\it Wang Professor of Computer Science,
Brown U.}
{\it ``The Many Faces of Concurrency''}
\item[9:55]{\bf Break}
\end{description}
\begin{center}
\subheading{Session 7}
\end{center}
\begin{description}
\item[10:20]{\it The Efficiency of Greedy Routing in Hypercubes and
Butterflies}
G.D. Stamoulis and J.N. Tsitsiklis, {\it MIT}
\item[10:45] {\it Balanced Routing:~~Towards the Distance Bound on
Grids}
M. Kunde, {\it TU Munich}
\item[11:10]{\it Parallel Algorithms for Routing in Non-blocking
Networks}
G. Lin and N. Pippenger, {\it U. British Columbia}
\item[11:35] {\it Fully-Adaptive Minimal Deadlock-Free Packet Routing
in Hypercubes, Meshes, and Other Networks}
G.D. Pifarr\'{e}, L. Gravano, S.A. Felperin, {\it ESLAI, IBM Argentina and
IBM Almaden;} J.L.C. Sanz, {\it IBM Argentina and IBM Almaden}
\end{description}
\begin{description}
\item[12:00]{\bf Lunch}
\end{description}
\begin{center}
\subheading{Session 8}
\end{center}
\begin{description}
\item[1:30]{\it A Framework for Proving Sequential Consistency of
High-Performance Shared Memories}
P. Gibbons and M. Merritt, {\it AT\&T Bell Labs;} K. Gharachorloo,
{\it Stanford}
\item[1:55]{\it Sequential Consistency versus Linearizability}
H. Attiya, {\it The Technion;} J.L. Welch, {\it U. North Carolina}
\item[2:20]{\it Detecting Violations of Sequential Consistency}
K. Gharachorloo, {\it Stanford;} P. Gibbons, {\it AT\&T Bell Labs}
\item[2:45]{\it Impossibility Results for Asynchronous PRAM}
M. Herlihy, {\it DEC}
\end{description}
\begin{description}
\item[3:10]{\bf Break}
\end{description}
\begin{center}
\subheading{Session 9}
\end{center}
\begin{description}
\item[3:45] {\it Understanding Retiming through Maximum
Average-Weight Cycles}
M.C. Papaefthymiou, {\it MIT}
\item[4:10] {\it A One-Way Array Algorithm for Matroid Scheduling}
M.F.M. Stallmann, {\it North Carolina State University}
\item[4:35] {\it On the Capabilities of Systolic Systems}
S. Even, {\it The Technion and Bellcore;} A. Litman, {\it Bellcore}
\end{description}
\begin{description}
\item[5:00]{\bf Adjourn}
\end{description}
\endgroup
\newpage
\heading{General Information}
{\bf Location:} All conference events will take place at the
oceanfront Marriott Resort on Hilton Head Island in South Carolina.
Hilton Head Island is one of the East Coast's most popular vacation
resorts, featuring golf, tennis, sailing, windsurfing, horseback
riding, deep sea fishing, parasailing, volleyball, hiking, biking,
skating, birdwatching, sunbathing, surfing, swimming, and many other
recreational activities.
{\bf Registration:} A registration desk will be open from 7:00pm until
10:00pm on Sunday, July 21, and during the day on Monday through Wednesday.
\medskip
{\bf Climate:} Midsummer temperatures are hot: the maximum temperature
of about 89F and minimum humidity of 55\% to 60\% occur between noon
and 2 p.m.
The temperature remains below 91F for more than half the days of July.
The climate is mediated by a seven mile per hour offshore breeze
which develops sometime before noon and continues until late afternoon.
Frequent thunderstorms drop a total
of 7 inches of rain in July. Nonetheless, the percent of sunshine is
high (65\% to 70\%) and two thirds of the days receive fewer than one tenth of
an inch.
\medskip
{\bf Transportation:} The Marriott Resort is located a few minutes (by
car) from the Hilton Head Airport. Hilton Head is located about an
hour northeast of Savannah, Georgia, and about 2 hours southeast of
Charleston, South Carolina.
For domestic flights, American Airlines is
offering a 45\% discount
on full coach fare or a 5\% discount on any other fare into Savannah
or Hilton Head. American will offer a discount on international
travel but the amount is determined by the sales office of
the departure city. The discounts apply for
travel on Friday, 19 July through Sunday, 28 July.
You can reach American Airlines Meeting Services desk directly at
(800) 433-1790. Refer to STAR file 0271AJ.
For ground transportation from
Savannah, you can use Hilton Head Transport (HHT) to travel to the
Marriott at Hilton
Head at a cost of \$38 round trip.
They leave after every flight arrival
and arrive at the Marriott in one hour and 15 minutes.
All taxi service between the Hilton Head Airport and the Marriott
is owned by HHT and costs \$12.
Rental cars from Savannah and Hilton Head Island
range from \$31/day to \$40/day for weekdays depending
on the company and car.
We strongly encourage you to arrange your
air and ground transportation through Chris Lacey at Omega Travel
in Cambridge, MA (617) 868-0006 or (800) 777-7279.
For international flights, Omega will negotiate the discount
and itinerary with American Airlines and compare this with the rate and
itinerary of other carriers. Omega claims
to beat the price of 80\% of the international
itineraries supplied to their customers
by the airlines. For ground transportation, Omega will supply HHT
with a schedule of passengers flying into
Savannah and Hilton Head. Hilton Head Transport will then provide
a discount of approximately 20\% (depending on the total number of
participants) off their regular fare.
If enough participants arrive within a short window of time at either
airport, Omega will hire a dedicated van from HHT if
it is cost effective. With regard to rental cars,
Omega may be able to negotiate a discount with a
single company if a sufficient number of people arrange their
rental cars through Omega.
If Chris Lacey is not available at Omega Travel, ask for Maureen Delia,
Nancy Schram, or Felix Lena. They will also be familiar with
the SPAA '91 account.
\medskip
{\bf Hotel and Island Information:} The biggest natural attraction of the
Marriott Hilton Head Resort
is the Atlantic Ocean---the hotel is located on beachfront property.
In addition, the hotel
has the usual array of amenities including indoor and outdoor
swimming pools, exercise room, saunas, and whirlpool.
Day care for children at least five years of age is provided
by the recreation department of the hotel for a \$12 fee for the
day and a \$15 fee for the evening. The hotel will arrange for
on-site babysitting for younger children as long as you notify them
24 hours in advance.
Hilton Head Island has a vast number of golf courses and tennis courts.
Within shouting distance of the Marriott is the Shipyard Plantation
Golf and Racquet Club which features 27 holes of PGA championship
golf and 20 tennis courts. In addition to golf and tennis,
Hilton Head offers a huge variety of other activities such as
sailing, wind surfing, horseback riding, deep sea fishing,
and parasailing. There are also numerous boat tours of the
surrounding islands and tours of Beaufort, Savannah, and Charleston.
For those who wish to use their own steam to get around the
island there is an extensive system of bicycle trails and,
of course, plenty of vendors renting bikes and rollerblades.
For those more interested in nature than sport, Pinckney Island
is adjacent to Hilton Head Island. This National
Wildlife Refuge features fourteen miles of trails and
excellent birding.
Information on all these activities will be included in your registration
packets.
\medskip
{\bf Sunday Activities:} Given the plethora of options, there is no
excursion planned for Sunday, July 21.
However, if you want to play golf and/or tennis that day please indicate so
on the registration form. The island is very busy at
this time of year and this will assist us in making a block of
reservations for court and tee times. For example if you want to make
reservations for two for golf simply write 2 next to golf on the
registration form. Or, for example, if you do not have a partner for
tennis but
anticipate playing for two hours indicate so on the form. We'll
provide a list of people without partners at the registration desk.
If enough people indicate that they are interested in beach volleyball, we can
arrange for the Marriott to set up a court on Sunday afternoon.
Those interested in exploring Pinckney Island on Sunday should indicate
so. If there is enough interest we will arrange group transportation.
You may make reservations on the registration form for more than one
activity if you feel you will have time.
\medskip
{\bf Reception and Banquet:} There will be a reception for all
registrants from 7:00pm until 10:00pm on Sunday evening at the
Marriott. The conference banquet will be at 7:30pm on Tuesday evening.
\medskip
{\bf Open Problem Session:} There will be an informal open problem
session on Monday at 5:30pm. Participants will be allotted 5 minutes
to present open problems and (if time permits) to state recent
research results.
\medskip
{\bf Business Meeting:} There will be a business meeting at 9:00pm on
Monday evening. All registrants are encouraged to attend. A variety of
subjects will be discussed, including the location, size, and scope of
future SPAAs.
\medskip
{\bf Further Information:} For further information, contact Bill
Aiello, MRE-2P363, Bellcore, 445 South Street, Morristown, NJ 07960,
(201) 829-4872.
\medskip
{\bf Student Support:} Some travel money may be available for students
wishing to attend SPAA '91. Priority will be given to speakers and
authors with insufficient funds. If interested, please contact Alok
Aggarwal at the IBM T.J. Watson Research Center, P.O. Box 218, Yorktown
Heights, NY 10598, (914) 945-2027.
\end{document}
--
=========================== MODERATOR ==============================
Steve Stevenson {steve,fpst}@hubcap.clemson.edu
Department of Computer Science, comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell