Figure 1: Number of hosts with given amounts of floating-point computing power
Abstract
|
Volunteer computing is a paradigm in which
Internet-connected computers, volunteered by their owners,
are used as a source of computing power and storage.
This paper studies the potential capacity of volunteer computing, in terms of several types of resources (processing power, memory, disk space, and network bandwidth), combinations of these resources, and change in these resources over time. We also study factors that affect the usability of these resources, such as the fraction of time hosts are powered on, user-specified limits on resource usage, and host churn. Our study is based on data collected from about 300,000 hosts participating in a volunteer computing project over a period of 8 months. |
Volunteer computing is a computing paradigm that uses large numbers of computers, volunteered by members of the general public, to provide computing and storage resources. Ref Saramenta.
Early volunteer computing projects include the Great Internet Mersenne Prime Search (GIMPS) [GIMPS], SETI@home [SAH], and Folding@home [FAH]. Volunteer computing is being used in high-energy physics, molecular biology, medicine, astrophysics, climate study, and other areas.
These projects have tens or hundreds of thousands of participants, and correspondingly large computational and storage capacity. For example, SETI@home has sustained a processing rate of about 100 TeraFLOPS for several years.
This paper studies the limits of performance of volunteer computing.
The volunteer computing projects to date have primarily been throughput-oriented (i.e. minimal latency constraints), and have relatively small requirements in terms of memory, disk, and network bandwidth. However, we are interested in the potential of volunteer computing for applications with requirements in terms of:
High-performance computing (low turnaround) versus high-throughput computing.
Our primary source for this study is a database of host information collected by the SETI@home project. SETI@home is based on BOINC (Berkeley Open Infrastructure for Network Computing), a middleware system for volunteer computing.
The data in this paper reflects a snapshot of the SETI@home database taken on November 18, 2005. The data reflects the population of hosts that were actively participating at that time - i.e. those that had returned completed work within the past week.
BOINC enables the creation of volunteer computing projects. Each project publicizes itself (by a web site and other means) in order to attract participants.
A BOINC participant runs a program called the BOINC client on their computers. This program typically is started on boot-up, and runs whenever the computer is powered on. Using this client, they can 'attach' the computer to any number of BOINC projects. They can also control what fraction of the computer's resources (such as CPU time and disk space) are allocated to each project.
Participants can specify 'preferences' that limit when and how BOINC can use their computer resources. For example, they can specify that no computation should be done when the computer is in use (as evidenced by keyboard or mouse input). They can specify limits on the times of day when BOINC should do computation or network communication, and the period between network activity.
Participants specify a resource share for each
The BOINC client periodically measures the hardware characteristics of the computer. It also measures quantities related to the usage of the computer, such as the fraction of time it is powered on, the fraction of time it has a network connection, and so on. The BOINC client avoids collecting information that might be viewed as an invasion of privacy (e.g. what specific hours the computer is in use).
The BOINC client periodically contacts a scheduling server at each of the projects to which is attached, reporting the computer's hardware and usage characteristics. The scheduling server replies with a set of instructions for doing work. This typically involves downloading executable files, and input files, running the applications against the input files, and uploading the resulting output files.
The BOINC client executes the following benchmarks:
A multiprocessor machine with N CPUs typically has lower performance than N times the speed of a single CPU. The difference is especially great for multi-core architectures, such as Intel 'hyperthreaded' CPUs, that share a single floating-point unit between cores. To reflect this, BOINC's benchmark all CPUs simultaneously. Specifically:
TABLE FOR # CPUS
The BOINC client measures and reports the amount of
physical memory (RAM) and swap space.
This presents a somewhat incomplete picture: it doesn't
The BOINC client measures the average throughput of network file transfers. More specifically, it measures throughput during all periods when file transfers are in progress (many file transfer may be active simultaneously) and it maintains and exponentially-weighted average of these values.
The throughput measured by the BOINC client reflects several factors:
The BOINC client measures the amount of total and free disk space
on the volume where it is installed.
BOINC doesn't measure space on volumes other than the one on which it is installed, so it may underestimate available disk space on some machines. Conversely, it may overestimate disk space in situations where several computers share a single network-accessible volume, and run BOINC from that volume.
CHANGE OVER TIME
Hardware resources are useless in isolation.
Disk space is useful only if there is network bandwidth
available to access it,
and CPU power is useful only if there is memory in which to execute.
BOINC participants, during the registration process, can specify their country. In this way hosts are associated with countries. The breakdown is shown in Table X.
BOINC doesn't verify that participants are actually from
the country they indicate.
However, the breakdown roughly agrees with data collected
via the BOINC client, which obtains and reports the time zone
(offset from Greenwhich Mean Time) of the host,
and reports it to the scheduling server.
The distribution of time zones is shown in Figure X.
Participants can specify whether their computer is at home, school, or work. We call this the venue. If they have multiple computers, they can assign them separate venues, and can define a different set of preferences (see Section X) to each venue. For example, computers at work might be configured to run BOINC applications only at night.
The breakdown among venues is shown in Table X.
Number of hosts on the Internet
Jul 2005 353,284,187 Jan 2005 317,646,084 Jul 2004 285,139,107 Jan 2004 233,101,481 Jan 2003 171,638,297 Jul 2002 162,128,493 Jan 2002 147,344,723 Jul 2001 125,888,197 Jan 2001 109,574,429 Jul 2000 93,047,785 Jan 2000 72,398,092 Jul 1999 56,218,000 Jan 1999 43,230,000 Jul 1998 36,739,000 Jan 1998 29,670,000
Relevance to data storage applications
The BOINC client measures several aspects of computer usage.
The fraction of time during which
the BOINC client is running on the host
is called the 'on-fraction'.
On most hosts, this is about the same as the fraction of time
the host is powered on,
since BOINC starts automatically at boot-up
and runs in the background all the time.
The mean on-fraction is 0.807,
and the distribution is shown in Figure X.
The fraction (of the time that BOINC is running)
that a physical network connection exists is called the 'connected-fraction'.
For hosts with LAN and DSL connections, this is close to 1.
For hosts with telephone-based (ISDN or modem)
or wireless connections, it may be lower.
The mean connected-fraction is 0.831,
and the mean is shown in figure X.
There may be periods when, although BOINC is running, it is not allowed to execute applications or transfer files. This can occur when
Not all CPU time is available to BOINC: other CPU-intensive programs may run on some computers. BOINC does not directly measure CPU load. However, it does maintain, for each project, the 'CPU efficiency', which is defined as average number of CPU seconds accumulated by that project's applications per second of wall time during which they are runnable. This reflects two factors:
BOINC allows participants to specify (through a web-based interface) various preferences that limit how and when BOINC uses their hardware resources. These preferences include:
Run on batteries: this indicates that BOINC should run be active (i.e., run applications and do network communication) even if the computer is running on batteries. It's relevant primarily to laptops. The default is No. 10.2% selected Yes.
Run if user active: This indicates that BOINC should be active even if there has been user input (mouse or keyboard) in the last three minutes. The default is No. 71.9% selected Yes.
Limited computing hours: Users can specify a range of hours during which BOINC is active. 3.3% of users specified such a range, and the average duration was 12.41 hours.
Limited communication hours: Users can specify a range of hours during which BOINC may do network communication. 0.8% of users specified such a range, and the average duration was 12.18 hours.
Leave applications in memory: Users can specify whether application remain in memory when preempted by BOINC. The default is No; 9.6% selected Yes.
Confirm before connecting: Users can specify that BOINC should get their permission (via a dialog) before doing network communication. This is primarily relevant to modem users. The default is No. 8.4% selected Yes.
Hangup if dialed: Users can specify that BOINC should hang up a modem connection when it no longer needs it. The default is No. 60% selected Yes.
Minimum connection interval: Users can specify a target minimum time between network communication. This has two purposes: 1) it lets modem users (who often pay a fee per connection) concentrate communication into infrequent bursts; 2) if a computer is sporadically connected (e.g. a laptop) it lets the user make sure that enough work is fetched to keep the computer busy. The default is 0.1 days. The average setting is 0.69 days.
Disk access interval: Users can specify a minimum time between disk accesses. This is relevant primarily to laptop users whose computers have a low-power mode in which the disk doesn't rotate. The default is 60 seconds; the average setting is 78.9 seconds.
Disk maximum used: Users can specify the maximum amount of disk space used by BOINC. The default is 100 GB. The average setting is 63.6 GB.
Disk maximum percent used: Users can specify the maximum percentage of total disk space used by BOINC. The default is 50%. The average setting is 42.6%.
Disk minimum free Users can specify the minimum amount of free disk space. (When free space falls below this level, BOINC deletes files). The default is 0.1 GB. The average setting is 0.97 GB.
Because anonymously volunteered computers can't be trusted, many volunteer computing projects use redundant computing to minimize the effect of malicious or malfunctioning hosts. In this technique, each job is executed twice on hosts belonging to different volunteers. If the results agree (within application-defined thresholds) they are accepted; otherwise a third instance is executed, and so on. Redundant computing decreases available computing power by a factor of slightly more than two.
Combining the various factors we have presented, and assuming that the factors are statistically independent, we have the following expression for the total computing power X available to a project:
X = Xarrival * Xlife * Xncpus * Xflops * Xeff * Xonfrac * Xactive * Xredundancy * Xshare
Where Xarrival is the average arrival rate of hosts, Xlife is the average lifetime of hosts, Xncpus is the average number of CPUs per host, Xflops is the average FLOPS per CPU, Xeff is the average CPU efficiency, Xonfrac is the average on-fraction, Xactive is the average active-fraction, Xredundancy is the reciprocal of the average redundancy, and Xshare is the average resource share (relative to other CPU-intensive projects).
For applications that use large amounts of RAM or disk, this estimate must be scaled by the factors described in sections X and Y. Analogous expressions estimate the limits of storage capacity and network transfer.
To what extent can volunteer computing handle data-intensive tasks? Foster et al. discuss this question [REF], and point out that while SETI@home processes about 25 KB of data per CPU hour, some physics applications have a much higher ratio. They cite applications that process 60 MB and 660 MB per CPU hour.
To study this question, we define the 'data processing rate' R of an application to be the average number of bytes of data it processes using 3.6e11 floating-point operations (i.e. one hour of CPU time on a 1 GFLOPS computer). we assume that a client is able to do both computation and communication nearly all the time (the BOINC client program overlaps these activities, and network communication takes little CPU time).
Suppose a 1 GFLOPS computer has a 1 Mbps network connection. Then it can download 450 MB per hour. If it runs an application for which R=450MB, then both network and CPU are saturated (i.e. busy all the time). If R < 450MB, the network is not saturated; if R > 450MB, the CPU is not saturated (of course, the excess CPU time could be used by a less data-intensive project).
This critical value of R varies with the host;
it will be smaller if the host has a faster CPU or a slower network connection.
For a given value of R, some fraction of the host population
will be network-saturated and won't be able to devote all their CPU time
to the application.
Figure X illustrates this effect,
showing the FP processing capacity available to
applications with various values of R.
It can be seen that considerable processing power is available
even to applications with R = 100MB or 1GB.
In other words, volunteer computing can potentially handle
data-intensive applications.
This analysis omits some important factors: saturating lots of client network connections could swamp the outgoing server links, ISP backbone networks, and shared incoming links. Solving these problems is an entire research agenda; we believe that an approach based on gleaning unused network bandwidth could yield progress.
Sarmenta [REF] originally articulated the idea of volunteer computing, and he also explored many of its technical aspects. The Entropia [REF] and XtremWeb [REF] projects have studied the speedup of various applications in the context of volunteer computing, but not characteristics of hosts.
Acharya and Setia studied the availability of idle RAM on workstation pools, and the statistics of its periods of availability - something we have not addressed.
We have presented an analysis of the hardware resources present in a typical volunteer computing project, and have described the other factors that affect the computing power and storage capacity available to the project.
A snapshot of the SETI@home host database is make every day, and we have an archive of these for a period of about 10 months. This could provide interesting data about the change in resources over time. We made some initial studies, but the results were inconclusive; at the beginning of the period, participants were 'early adopters' and typically had fast machines on fast networks. Many of the participants who arrived later had lower-end machines. Thus, some performance measures actually declined over the interval.
We thank Rom Walton, Matt Lebofsky, and a number of volunteer open-source programmers for their help in collecting performance data. This work was funded by the National Science Foundation under aware XXX.