SCIENTIFIC PROGRAMMING
Editor: Paul F. Dubois, dubois@users.sourceforge.net

SETI@HOME—MASSIVELY DISTRIBUTED COMPUTING FOR SETI
By Eric Korpela, Dan Werthimer, David Anderson, Jeff Cobb, and Matt Lebofsky

S

INCE RADIO’S EARLIEST DAYS, PEOPLE HAVE CONSIDERED
THE POSSIBILITY OF DETECTING SIGNALS FROM AN EX-

TRATERRESTRIAL CIVILIZATION—AND SINCE THE ADVENT OF RADIO ASTRONOMY, THE TOOLS TO PERFORM SUCH A SEARCH HAVE

existed. Starting in the late 1950s, researchers have been performing progressively more sensitive searches, buteach search has been limited by thetechnologies available at the time. As radio frequency technologies have become
more efficient and computers have become faster, the searches have grownlarger and more sensitive. The
SETI@home project, managed by agroup of researchers at the Space Sciences Laboratory of the University ofCalifornia, Berkeley, is the first attempt
to use large-scale distributed computing
to perform a sensitive search for radio
signals from extraterrestrial civilizations.
A radio SETI tutorial

You might wonder why an enormous supercomputer would be necessary to detect radio signals from analien civilization. It might seem to be afairly simple signal-processing task.
Such a supercomputer is needed primarily because• the parameters of an alien signal areunknown, and• the sensitivity of a search for extraterrestrial intelligence (SETI) depends fairly heavily on the available
processing power.

78

Our search for extraterrestrial intelligence assumes that an alien civilization wishing to make contact withother races would broadcast a signalthat is easily detectable and easily distinguishable from natural sources ofradio emission. One way to achievethese goals is to send a narrowband signal. By concentrating the signal power
in a very narrow frequency band, thesignal will stand out among the natural
broadband sources of noise.
Consequently, radio SETI efforts haveconcentrated on detecting narrowband
signals. When searching for narrowband
signals, it is best to use a narrow searchwindow (or channel) around a given frequency. The wider the channel, the more
broadband noise is included in addition
to any signal, which limits the system’s
sensitivity. Early systems used analog
technology to create narrow bandpass
filters that could observe at a single frequency channel. More recent systems
use massive banks of dedicated fast
Fourier transform (FFT) processors toseparate incoming signals into up to abillion channels, each 1 Hz wide.
Unfortunately, this technique is limited. For one thing, extraterrestrial signals are unlikely to be stable in frequency because of transmitter andreceiver accelerations. For example, a
receiver listening for signals at 1.4
GHz located on the earth’s surface undergoes acceleration of up to 3.4 cm/s2
because of the earth’s rotation. Thatmight not seem like much, but it corresponds to a Doppler drift rate of 0.16
Hz/s. If uncorrected, an alien transmission would drift out of a 1-Hz
channel in about 6 seconds, effectively
limiting the maximum integration timeto 6 seconds. Because of the inverse relationship between maximum frequency resolution and integration time∆υ = (1/∆t), there is an effective limit
to the frequency resolution that we canobtain without correcting the received
signal for this effect (∆υ ~ 0.4 Hz).
In principle, we could correct formost of the drift resulting from theearth’s motions, but how do we correct
for an unknown planet’s motions? Analien civilization narrowly beaming
signals at the earth could correct theoutgoing signal for the transmitter’s
motions, but a civilization transmitting
an omnidirectional beacon could not
make such an adjustment. Therefore,
to search for this type of signal at very
narrow bandwidth (<< 1 Hz) and thehighest possible sensitivity, we would
need to correct for Doppler drift at thereceiving end and search for signals at
multiple Doppler drift rates. Repeating an analysis at multiple Doppler
drift rates becomes compute intensive.
Other signal parameters are still unknown—for example, at what frequency will it be transmitted? What is
its bandwidth? Will it be pulsed? If so,

COMPUTING IN SCIENCE & ENGINEERING

Figure 1. SETI@home uses the National
Astronomy and Ionospheric Center’s
305 meter telescope at Arecibo, PuertoRico. The inset at right shows the detailsof the “carriage house” structure. The
SETI feed is the vertical structure extending downward from the carriage
house. (Photos courtesy of NAIC—
Arecibo Observatory, a facility of the
NSF. Photos by David Parker and Tony
Acevedo.)at what period? Fully investigating awide range of these parameters requires
proportionally larger computing power.
In addition to detecting a signal, we
must determine whether a signal is trulyof celestial origin. The vast bulk of thenarrowband signals received by a radio
telescope consists of locally generated
radio frequency interference (RFI). Fortunately, RFI has properties that let us
distinguish it from extraterrestrial emission. But again, this RFI elimination requires computing resources.
Performing all of these calculations
for even a small portion of the radio
spectrum would require more computational power than is available in thelargest existing supercomputer.
Distributing the load

Fortunately, searching for signals ina data stream from a radio telescope isan easily distributed task. We can breakup data from an observation into frequency bands that are essentially independent of one another. In addition, an
observation of one portion of the sky isessentially independent of an observation of another part. This lets us dividea large dataset into small chunks that apersonal computer can analyze comparatively quickly. In this way, we candistribute the work to people willing to
donate their spare CPU cycles.
SETI@home conducts its observations at the National Astronomy and
Ionospheric Center’s 305-meter radio
telescope in Arecibo, Puerto Rico (seeFigure 1). The project uses a dedicatedfeed (the nearly vertical structure suspended left of the center of the dish,shown in the expanded view) from the

JANUARY/FEBRUARY 2001

receiver mounted opposite the primaryobserver’s feed (the enclosed dome-likestructure to the right) on the Arecibo
telescope’s carriage house. This uniquearrangement lets us conduct SETI@
home observations without interference with other uses of the telescopeand results in three main modes of observation. If the primary feed is stationary, objects in the sky pass throughthe SETI@home instrument’s field ofview (0.1 degrees) at the rate of theearth’s rotation (also known as the sidereal rate). An object would require
about 24 seconds to transit the field. If
the primary observer is tracking asource in the sky, the SETI@home receiver’s beam slews across the sky at
twice the sidereal rate. Occasionally,other observers could use the SETI@
home feed to track objects on the sky.
During the project’s course, SETI@
home will view most portions of the sky
visible with the Arecibo telescope three ormore times. This includes stars with declinations (the celestial equivalent of latitude) between –2° and 38°, thoroughly
covering about 25% of the sky.
The SETI@home system records a
2.5-MHz-wide band centered at the
1,420 MHz hydrogen line. Because thisline would be of interest to astronomersof any species who were studying thegalaxy, this frequency is one of the most
likely locations for deliberate extraterrestrial transmissions. This 2.5-MHzband is recorded continuously onto 35Gbyte DLT tapes using 2-bit complex
samples. Each tape holds about 15.5
hours of data. The entire sky survey is

expected to require 1,100 tapes, for a
total of 39 Tbytes of data.
The recorded tapes are shipped toBerkeley, where we subdivide them into
small work units on four splitter workstations. We divide the 2.5-MHz bandwidth data into 256 subbands by meansof a 2,048-point FFT followed by 256
eight-point inverse transforms. Because
the 9,766-Hz-wide subbands are divided
into lengths of 220 samples, each work
unit corresponds to about 10 kHz of
bandwidth and 107 seconds of duration.
Subsequent work units overlap by 20 to
30 seconds to allow full analysis of signals that might be within a beam transit
time of the end of a work unit. We transfer each work unit to temporary storage(capable of holding about 750,000 work
units) for distribution to users.
The main SETI@home server (Figure 2) consists of three Sun Enterprise
450 series computers. One holds theuser database, containing information
on each of the 2.4 million SETI@home
volunteers (including the number ofwork units completed, time of last connection, and team membership). The
user database also holds information on
the amount of work done by each typeof microprocessor architecture and byeach operating system to which SETI@
home has been ported.
The second server system holds thescience database in an ever-expanding
array of redundant disks (currently a
432-Gbyte RAID 0+1). The science
database contains information on thetime, sky coordinates, frequencies, andso forth for each work unit generated,

79

SCIENTIFIC PROGRAMMING
Figure 2. Structure of the SETI@home
data server.

Science database

Data server

Tapes
from
Arecibo

Data splitters

Work unit
storage

as well as information about how manytimes the work unit has gone to
SETI@home users and how many results have been received.
The largest portion of the science
database capacity stores the parametersof potential signals (such as signal
power, frequency, and arrival time sky
coordinates) detected by SETI@home
volunteers. As of October 2000, thedatabase contained 1.1 billion candidate signals (before RFI rejection).
The third server system contains thework unit storage, handling distribution of work units and storage of returned results. Communications between the server and clients use thehypertext transfer protocol (HTTP).
We chose this protocol because manyInternet volunteers might be behindfirewalls that prohibit most traffic but
permit access to the World Wide Web.
The server supports two types of request. The first requests a work unit.
The response to this request includes awork unit chosen from temporary storage. Priority goes to those units thathave not previously been sent or thosethat were sent but for which no results
were received.
In the second type of request, theclient program returns a result to theserver. The server inserts the candidate
signals contained in the result into thescience database and updates the volunteer’s statistics in the user database.
The response to this request includes
the volunteer’s statistics so that theclient program can display them.

80

The
internet
2.4 million
users
User database

The SETI@home client program

SETI@home currently distributes
client software for 47 different combinations of CPU and operating system.
Users can download the software fromthe SETI@home Web site (http://
setiathome.ssl.berkeley.edu). For Microsoft Windows and Apple Macintosh, the software installs itself by default as a screen saver (Figure 3), only
processing data when the screen saver
is active. For other platforms, the basic
client is text based. Users of these platforms generally run the client in the
background. A graphical display program similar to the Mac and Windows
versions is available for Unix systems
that run the X Windows system. In addition, a wide variety of third-party applications have been developed for display of data, detected signals, sky maps,
and volunteer statistics.
After receiving a work unit, theclient performs a baseline smoothing
on the data to remove any wideband(∆υ > 2 kHz) features. This prevents
the client from confusing fluctuationsin broadband noise (due in part to variations in the hydrogen line emission as
the field of view transits the sky) withintelligent signals. The client then begins the main data analysis loop, shown
schematically in Figure 4.
At the start of each passage throughthe loop, the data is transformed into an
accelerated frame of a given Doppler
drift rate. The drift rates at which theclient searches the data for signals varyfrom –10 Hz/sec to +10 Hz/sec (accel-

erations expected on a rapidly rotating
planet) in steps of 0.0018 Hz/sec. The
client also examines the data at Doppler
drift rates out to ±50 Hz/sec (accelerations of the magnitude that would arise
from a satellite in low orbit about anearth-like planet), but at a more coarse
step of 0.029 Hz/sec. A signal from analien world would most likely have anegative drift rate (as the accelerations
involved would be away from the observer). Despite this, we examine both
positive and negative drift rates for the
purpose of statistical comparison and toleave open the possibility of detecting adeliberately chirped extraterrestrial
signal.
At each drift rate, the client searches
for signals at one or more bandwidths
between 0.075 and 1,221 Hz. This isaccomplished by using FFTs of length
2n (n = 3, 4, ..., 17) to transform the data
into a number of time-ordered power
spectra. To avoid repeating work, notall bandwidths are examined at every
Doppler drift rate. Only when thechange in drift rate becomes significant
compared to (1/∆υ2) does the program
compute another FFT of a given
length. Therefore, 32K-point transforms are performed one quarter as often at 64K-point transforms.
The transformed data is examined forsignals that exceed 22 times the meannoise power. This threshold corresponds to 7.2 x 1025 W/m2 at our finest
frequency resolutions, or the equivalentof detecting a cell phone on one of themoons of Saturn. The SETI@home
client reports any such spike signals in
the resulting transmission.
If there is sufficient time resolution
in the transformed data (n < 15) and the
SETI receiver is not tracking an object
on the sky, the client examines it for
signals that match the telescope beam’s
parameters. As a radio source drifts
through the field of view, the measured

COMPUTING IN SCIENCE & ENGINEERING

Figure 3. A screenshot of the SETI@home
client program. The bottom half of thescreen presents the power spectrum currently being analyzed. The upper left
shows analysis state and the results ofthe current analysis. The upper right section shows information about the data
being processed and user statistics.

power will vary depending on the telescope’s beam profile, which is approximately Gaussian. The SETI@home
client performs a weighted χ2 fit on any
signals that exceed 3.2 times the meannoise power and reports those forwhich the goodness of fit exceeds a certain level. This power level typicallycorresponds to 8.4 x 10–25 W/m2.
The client then divides transformed
data at each frequency into chunkswith duration equal to the time required for an object to transit the telescope field of view. Two algorithms
serve to analyze these chunks forpulsed signals. The first algorithm, thetriplet finder, searches each chunk forthree evenly spaced signals that eachexceed 7.75 times the mean noise
power (as little as 5.3 x 10–25 W/m2)
and report any detected signals.
The second algorithm is a modified
fast-folding algorithm. A folding algorithm divides the data into chunks of duration equal to the period being searchedand co-adds them to improve signal-tonoise ratio. An FFA performs this function on a large number of periods without duplicating additions. The SETI@
home folding algorithm searchesroughly N log N pulse periods, where N
is the length of the input array. This
corresponds to periods between two
samples and N/3 samples. During a typical run of the client, this typicallymeans half a million periods between 2
ms and 10 s. The program computes
the threshold for detecting a pulsed signal dynamically to match the number ofco-added samples. This threshold canbe as low as 0.04 times the mean noise
power for pulses with periods less than
10 ms. This corresponds to pulse energies of about 1.8 × 10–26 J/m2.

JANUARY/FEBRUARY 2001

Depending on the individual work
unit’s parameters, this processing loop
requires 2.4 to 3.8 trillion floatingpoint operations (Tflop). It takes a typical (500 MHz) home computer 10 to
12 hours to complete a work unit. For
an average work unit, the SETI@home
client would report eight signals—four
spike signals, one Gaussian, one pulsed
signal, and one triplet signal.
Postprocessing

When the client has done its work,
the job isn’t done. Typically, theSETI@home client program returns a
few potential signals per work unit. Of
course, not all of these signals are evidence of extraterrestrial intelligence.
Errors made in the processing computers cause some of the signals. Typical numeric processors, memory, anddisk systems are fairly reliable. How-ever, SETI@home uses thousands ofyears of CPU time per day, magnifying
even low error rates. Even if undetected errors occur only on average
every 1018 machine instructions,
SETI@home would see several perday. Additional errors can be introduced in result transmission because of
broken connections or malfunctioning
HTTP proxies. To combat these effects, we examine each signal to see if
the parameters match their permitted
values. We also send each work unit tomultiple volunteers and cross-checkthe returned values to verify accuracy.
The vast majority of the database’s
signals are evidence only of terrestrial
intelligence. Sources of narrowband radio emission are ubiquitous where human technology is present. Even at the
Arecibo observatory, where care istaken to minimize interference, thisfor Doppler drift rates from -50 Hz/s to +50 Hz {for bandwidths from 0.075 to 1220 Hz in 2X steps {Generate time ordered power spectra.
Search for short duration signals above a constantthreshold (spikes)
for each frequency {Search for faint signals matching beam parameters(Gaussians)
Search for groups of three evenly spaced signals(triplets)
Search for faint repeating pulses (pulses)}}}
Figure 4. Pseudocode representation of the SETI@home algorithm.

81

SCIENTIFIC PROGRAMMING
Eric Korpela is a research astronomer at the Space Sciences Laboratory at
the University of California, Berkeley. In addition to his SETI work, he specializes in the study of interstellar matter and far ultraviolet astronomical instrumentation. Contact him at korpela@albert.ssl.berkeley.edu.
Dan Werthimer is director of the Serendip SETI programand chief scientist of SETI@home. He has published numerous scientific papers in the fields of SETI, radio astronomy, instrumentation, and science education, and is editor of Astronomical and Biochemical Origins and the Search for Life in the Universe.
David Anderson is the SETI@home project director andhas done extensive research in operating systems, distributed computing, and computer graphics. He recently joined the management team of the distributed computing provider United Devices as chief
technology officer.
Jeff Cobb is a software engineer and systems manager
for the UC SETI projects. He has been with the SETI
group for seven years, and has developed many of the algorithms used in
SETI@home.
Matt Lebofsky studied computer science and music
composition at Binghamton University, and currently
has two completely separate careers in both fields. (Seealso www.lebofsky.com.)istence and the largest computation
ever performed. While we were writing this paragraph, 60 new volunteers
joined the project.
The 1.1 billion signals in the SETI@
home database are being examinedwith the techniques we’ve described.
The rate at which we are currently examining signals is lower than the rate
at which new signals are being added tothe database, so we have looked in detail at only a fairly small fraction of thepotential signals. We will soon add another computer system to our server
setup to speed this processing along—
we hope to examine signals in real time
before too long. So far, none of the signals examined has shown evidence of
extraterrestrial intelligence.

S
noise is present, due to local equipment, aircraft, satellites, and othertransmitters. Fortunately, these terrestrial emissions are fairly easy to distinguish from an extraterrestrial signal.
A large fraction of RFI consists ofcontinuous narrowband signals generated at or near the observatory. An extraterrestrial signal will only be detected when it is within the telescope’s
field of view, and, for our scanningmode of operation, will only have limited duration. Any signal that exceeds
this duration must be terrestrial andmay be rejected.
Other RFI sources are of short duration and repeat on time scales of hours
to days. Therefore, any signal that repeats when the telescope is viewing a
different portion of the sky might also
be rejected.
After RFI is removed, the bulk of theremaining signals are due to random
fluctuations in the noise background82

mimicking an extraterrestrial signal. To
sort out the true extraterrestrials, we canlook for persistent signals. We expectthat an extraterrestrial signal will be present at a similar frequency the next time
we examine the same celestial location.
A status report

As of 23 October 2000, 2,438,045
volunteers had run the SETI@home
program. Of those, 519,725 were actively running the program and had returned a result in the previous two
weeks. These volunteers had donated a
total of 437,000 years of CPU time fora total 4.3 x 1020 flop. Currently, theaverage processing rate of computers
running SETI@home is 15.7 Tflops—
averaged since the start of the project,
the processing rate is 9.5 Tflops. To
our knowledge, SETI@home is thelargest distributed computation projectin existence. It could also be considered
to be the largest supercomputer in ex-

ETI@home was originally slated
to process two years worth of datafrom the Arecibo telescope. The
strong public response and new improvements to the client software haveprompted us to extend the survey.
SETI@home currently samples onlya small portion of the radio spectrum
and a small portion of the sky. The twomost obvious means of expanding its
capabilities are to expand the sky coverage and widen the frequency bandwidth. SETI@home II, currently under study, hopes to do both.
The best means of expanding the sky
coverage would be to add a SETI@
home recorder system to a southernhemisphere radio telescope. This
would let us increase our sky coverage
from about 25% to 75%. We are currently discussing the possibility with asouthern observatory.
The recording system currently limits our frequency bandwidth. By duplicating the recording system, we could
double SETI@home’s bandwidth coverage (and, of course, its data rate).

COMPUTING IN SCIENCE & ENGINEERING

Café Dubois
Adventures in CGI
A friend who works for a small nonprofit organization
asked me to help her learn to write a CGI program. A CGI
program is one that the Web server starts up in response tosomeone clicking a “Submit” button. The Web server receives the information from the form (such as name, address,
did you click the “Don’t give my name to all your friends”
button) and passes it on to the CGI program. You can write a
CGI program any way you like, but the most common ways
are to write it in C, Perl, or Python. Your program prints
HTML to the standard output, and that is what the user’s
Web browser displays (“Thanks for your order. Of course, weare backordering your product. We have no products on
hand, we just use your money to buy one and send it toyou.”). A CGI program lets you interact with things on yourserver such as databases, or send email, or calculate a page in
response instead of having a static page displayed.
I knew how to do all the hard parts. Decoding the information the server passes you is easiest in Perl or Python,
where there are library routines that do it for you.
I wrote a Python script that worked fine on my computerand sent it to my friend. She installed it into her IIS server
running on Windows NT and, of course, it didn’t work atall. There are a lot of things to check in such a situation, because when a server runs a CGI script it usually runs it asuser “nobody” (a user with very limited permissions) andthe environment in which the program is started is not thesame as when a real user runs it. Everything checked; still
no joy. Finally, she calls Microsoft support. I’ve had goodluck calling Microsoft when I’m a paying customer. They
seem to really stick with it to get you an answer. We get theanswer. It is profound:She had installed Python into C:\ProgramFiles\Python20.
I had installed Python into C:\Python20. Mine worked. Hers
didn’t. That’s right, the problem was the stupid space in thepath. I hate computers.

As in any voluntary organization, it’s
important that SETI@home be responsive to the desires of its volunteers, because the program’s success depends entirely on the volunteers who provide thecomputing resources. We will continue
to keep our volunteers informed of ourprogress and to share with them the science behind SETI. We will also work toshow our volunteers how they have individually contributed to the project byproviding information about potential
signals they have detected and the areasof the sky they have scanned.

JANUARY/FEBRUARY 2001

Nevertheless, writing CGI scripts can be a lot of fun. If
you want to try writing a CGI script for your Web site, twobooks I’ve used are Mark Lutz and David Ascher, Learning
Python, (O’Reilly Press, 1999); and Dan Berlin, CGI Programming Unleashed (Sams.net, 1996). If you need a Web server
to practice on, there is a little practice one that comes withPython, Microsoft Windows has a “personal Web server”
you can install, or of course you can set up Apache on any
Linux box you own. You usually are not allowed to put CGI
scripts on Web sites you get for free or at low cost.
Python Programming on Win32
Python Programming on Win32, by Mark Hammond andAndy Robinson (O’Reilly Press, 2000), teaches you how to
use Microsoft technologies such as COM from Python. For
example, you can use a script to create a Word document
or Excel database. That might be handy for convertingcode output into something usable, for example.

Acknowledgments
SETI@home is largely funded throughprivate donations. The SETI@home
team especially thanks the Planetary
Society, Sun Microsystems, Fujifilm,
the SETI Institute, and Friends of
SETI@home (private individuals) for
their contributions. Some corporate
contributions have been matchedthrough the University of California
Digital Media Innovation Program.
We would also like to thank
SETI@home volunteers everywhere
for their valuable contribution of theprocessing power that makes SETI@
home work.

References
1. S. Bowyer et al., “Twenty Years of SERENDIP,
the Berkeley SETI Effort: Past Results and Future Plans,” Astronomical and Biochemical Origins and the Search for Life in the Universe, C.B.
Cosmovici, S. Bowyer, and D. Werthimer,
eds., IAU Colloquium No. 161 (Editrice Compositori: Bologna), p. 667, 1996.
2. D. Anderson et al., “Internet Computing for
SETI,” Bioastronomy 99: A New Era in Bioastronomy, G. Lemarchand and K. Meech, eds., ASP
Conference Series No. 213 (Astronomical Society of the Pacific: San Francisco), p. 511, 2000.

83