Create your own supercomputer with Java

By combining Java with the Web's collection of computers, you too can have the processing power you crave -- without buying a Cray

1 2 Page 2
Page 2 of 2

As mentioned before, the results produced by the applets are transmitted back to the server using a different "channel" than that used for job requests. More specifically, the results get transmitted to one of many reply ports managed by the server. Each of these reply ports is also handled by its own thread. This arrangement performs more effectively than relying on a single port, since the result packets need a lot more processing on arrival than the simple job request packets emanating from the applets. If a single thread were to be responsible for just one global results port, then it would be overrun by packets and data would be lost. So by multiplexing the results channel over several ports and several threads, incoming data is much less likely to cause a server overrun. The actual number of reply ports is set to 3 by default, but can be configured by the webmaster to any number between 1 and 100.

The job specification UDP packet is mostly application-specific, except for the first 2 bytes of the packet. These encode the reply port to address when sending the results back. This small field is stripped from the packet before the packet is passed to the concrete applet that invoked requestJob(). For the record, our raytracing example simply adds a single 16-bit scanline number that completely specifies what the applet has to do (that is, the job spec). This means the total size of the job spec packet for our raytracer is just 4 bytes.

Let us fast-forward past all the raytracing code (the application-specific part) and follow events from the point where the applet calls returnResults(). The application applet deals only with its own application-specific messages, so it does not specify any reply ports to returnResults(). The underlying WorkerApplet stored the port address from the incoming job spec, so it can now send the results to that port.

Assuming all UDP packets arrived safely, here's what happens on the applet side:

  1. Get job spec
  2. Execute job
  3. Return results

A multitude of threads

The design of the JobMaster server is somewhat more complex as it relies on multiple threads servicing multiple UDP ports. The general structure is one of a single "master" thread and a configurable number of slave threads. The master thread simply loops endlessly, waiting for job requests to arrive and immediately replying with job specifications. You can follow the exact implementation of all this in method processJobRequests().

Like the master thread, each slave thread is responsible for one receive UDP port. Both entities (thread and port) are encapsulated in an instance of class ResultsReceiver. Every ResultsReceiver thread loops forever, "catching" the results from applets and passing these results to the main program. (See the run() method for the exact implementation).

Back in the JobMaster class, the results are processed in the collateResults() method, whose implementation is application-specific. In our raytracing example, the results are single scanlines of the image being generated. These scanlines are copied to an off-screen Image, which is used to redraw and refresh a window on the server console where the progress of the parallel task can be followed.

Classic multithreading pitfalls

At this point I need to explain more about how the server assembles the raytraced picture and how exactly jobs are issued. Although these are application-specific, the issues tackled for the raytracer will crop up in most DAMPP applications. To manage the whole process of distributing the raytracing algorithm to remote processors, the server maintains a central data structure: a simple array of booleans, with one boolean for each scanline of the image. In other words, IMAGE_HEIGHT flags. These flags are used to track which scanlines already have been generated and received, and which haven't.

When the server receives a job request, it simply picks the next scanline which has not yet been received, and tells the applet to work on this scanline. When method collateResults() receives a scanline from one of the receiver threads, it first checks whether this scanline is actually outstanding. The fault-tolerant design of DAMPP means more than one applet theoretically can be working on the same problem, so when two duplicate results are received, the result arriving last will be rejected as being redundant. This does not pose any problems, and in fact is just a side-effect of the robustness of the system.

The potential problem, though, lies in different threads accessing shared data structures and corrupting the structures' state. The core flags array is accompanied by a simple (int) counter that also tracks how many scanlines have been successfully received. These two objects form a non-atomic whole, which needs to be kept rigorously in sync for the server to perform its essential bookkeeping. Therefore a locking mechanism is required to modify or access the two objects atomically. This is achieved using Java's synchronized keyword.

Usually, the synchronized keyword is used on methods to mean that the entire method needs to be atomic with respect to some Java object. But when implementing multithreading systems, you have to watch out for a potential performance bottleneck: If many threads need to access a common structure, locking and releasing of this structure needs to be done as swiftly as possible. Otherwise you risk creating long queues of threads waiting to access the shared structure. You should only lock (in other words, use the synchronized keyword) on the set of statements which absolutely require them. In collateResults() I synchronize the code as tightly as possible, around the flags array object.

Warning: Prototype ahead!

First of all, the minimalistic reliance on UDP for all JobMaster-WorkerApplet communications means the rendezvous protocol currently is very brittle. If a job request or job specification UDP packet ever gets lost during this initial stage of the protocol, then the (current) WorkerApplet fails to detect this, resulting in the applet becoming silent (forever waiting for a UDP packet that will never arrive). The upcoming 1.1 java.net API contains the most convenient solution: enhanced UDP support that will allow timeouts to be generated when waiting for a UDP packet. These timeouts can then trivially be exploited to allow the applet to retransmit its packets until a reply finally gets through.

Secondly, at the declaration level, class JobMaster is declared as being a subclass of java.awt.Frame. This is because the JobMaster pops up an AWT window to display the raytraced image as it is being calculated by the World Wide Web itself. The window also contains a couple of buttons to reset the picture (start from scratch) and quit the server. This means the JobMaster class contains an event handler method to deal with button events too.

Since the discussed implementation of the DAMPP system is a proof-of-concept prototype, the server combines (rather monolithically) both application-specific code and code that could be abstracted into the server equivalent of WorkerApplet -- that is, an application-independent foundation class that programmers could subclass and extend to deal with any suitable parallel problem. Decomposing the current server into independent parts would be the next step towards a more flexible DAMPP implementation.

Joining the DAMPP club

The DAMPP system will not handle every type of parallel problem well. Problems ideally suited to DAMPP should exhibit the following characteristics:

  • application-specifc computations should be expressible in a small program (since applets need to contain most of this code)
  • sub-problems should be easily definable using few parameters (this is to keep job spec packets small)
  • nodes tackling a sub-problem should not have to exchange data with other nodes
  • the computed results should be of reasonable size (otherwise the JobMaster will not be able to handle the load of the results stream)
  • the problem should be allowed to run for hours or days

If a DAMPP system is used within the confines of a company's intranet, using a fast LAN backbone as the communication medium, then all these requirements can be relaxed or even ignored. The third requirement, though, would mean additional work on WorkerApplet before a flexible system would be obtained.

Mass hysteria, ethical considerations and "You scratch my back, I scratch yours."

I can already hear the storm of shouts: "Viruses! He's distributing computational viruses on the Net!" Calm yourselves. Nothing is further from the truth. DAMPP applets should be embedded only in pages that have been clearly labeled to contain such applets. Users will be able to use their own free will, anywhere in the world, to decide whether they wish to have their (currently wasted) background CPU power borrowed and employed to a useful end or not.

One way to counter the inevitable segment of people who will refuse to donate some of their idle CPU power is to use a DAMPP system on sites where users are currently getting a lot of goodies for nothing: news sites, shareware sites, entertainment sites, software upgrade sites, etc… All of these sites could quite ethically, in my humble opinion, trade some of their valuable Web content for some minute amount of processing on client machines. After all, Web surfing and downloading from the Web are two activities that leave the client processor idle most of the time (yes, even with downloads), so only the selfish will object to this spare processor capacity being used by the site from which he or she is taking so much. The alternative means the processor is only used to generate heat, and nothing more.

"Surprise, Surprise!"

What do you think has been running in the background while you were reading this article?

That's right! The DAMPP raytracing applet.

If you enable your Java console and check its contents, you should see that the applet has (most likely) already finished its brief calculation and returned its results to our server.

If the applet happens to still be running, and you strongly object to this applet's presence, just quit your browser and the applet will die with it… but possibly think again after the deed; your machine now sits idle again.

Laurence Vanhelsuwé is an independent software engineer. Self-taught, he dropped out of college and immediately started a professional career writing arcade games. He has worked on such diverse technologies as X.25 WAN routers, virtual reality flight simulation, Postscript, and real-time digitized video-based traffic analysis. Laurence thinks Java will revolutionize computer science by leveling the computing landscape into one pan-Java playing field.

Learn more about this topic

1 2 Page 2
Page 2 of 2