The Frugal System

The Frugal System is a metacomputing package that distributes jobs intelligently on a Jini network.

The Frugal package allows jobs to choose intelligently among the compute engines registered with a Jini lookup service. This package uses the Cost-Benefit Framework developed at the Johns Hopkins University. Decision-making strategies using this framework are competitive in both CPU and memory use with an optimal algorithm that knows the future. This theoretical result suggests that using this framework is an excellent way to keep memory free and CPU loads low. Extensive experiments confirm that it significantly outperforms traditional methods. The relevant paper is available as "An Opportunity Cost Approach for Job Assignment and Reassignment in a Scalable Computing Cluster" at http://www.cnds.jhu.edu/publications/. This package also includes a Jini-enabled compute engine that works with the Framework.

The competitive factor for this framework is O(log n); that is, it is guaranteed to produce memory and CPU loads no higher than O(log number_of_machines) times those the best possible algorithm achieves, even if that algorithm knows the future (which ours does not.)

This system's major drawbacks are as follows:

The logarithmic factor above can be substantial.
The real-world environments this package functions in have less information than the framework requires. The approximations used can violate the framework's competitive guarantee in certain degenerate cases.

More importantly, however, it has the following benefit:

This system's algorithm, in its natural and approximated forms, has been thoroughly tested against standard resource allocation methods. In experiments, it performs much better than they when system loads are high - that is, when good performance is most important.

Starting Up the Package

First, choose a collection of machines that will perform work for the users of this package. These machines will merge conceptually into your metacomputer - a self-balancing computer of much greater computational power than the individual machines.

Step 1: System Setup

Optionally, design a security policy for use with this package. (This document assumes that this policy is found at /files/Frugal/yourpolicy.)
Run an HTTP server to provide RMI-using classes with downloadable code. (This document assumes that our package is available at http://yourname.com/Frugal/)
Run an RMI daemon.
Run a Jini lookup service.

Step 2: Compute Engines

For each machine in your metacomputer, choose a persistent storage location. For example, the third machine might have persistent storage at /files/Frugal/FrugalResource3State.
Start a Jini-enabled compute engine on each machine, as with:

   [start] java -cp 
      /files/jini1_0/lib/jini-core.jar:
      /files/jini1_0/lib/jini-ext.jar:
      /files/jini1_0/lib/sun-util.jar:
      /files/Frugal/FrugalResource.jar
   -Xmx32m
   -Djava.rmi.server.codebase=http://yourname.com/Frugal/FrugalResource-dl.jar
   -Djava.security.manager=java.rmi.RMISecurityManager   
   -Djava.security.policy=/files/Frugal/yourpolicy
   edu.jhu.cnds.Frugal.FrugalResourceServer
   [-f] /files/Frugal/FrugalResource3State [&]

   Use [start] on Windows machines, [-f] the first time you use this
   compute engine, and [&] on UNIX machines.

Each time you run this, a Frugal Resource appears on the local lookup service. After a short initialization period, it can perform work for other machines. It cannot accurately assess its own cost.

Step 3: Frugal Manager

Important Note: A Frugal Manager automatically "manages" every Frugal Resource it finds on the lookup services/groups it connects to. You can safely have two Frugal Managers managing identical groups of machines, for redundancy in case of machine crash. You can safely have two Frugal Managers managing non-intersecting groups of machines. However, it's not a good idea to have two Frugal Managers managing overlapping but non-identical groups of machines. The Frugal Managers will function correctly, but the Frugal Resources will publicly display the wrong costs to a lookup browser. More importantly, the theory does not guarantee good behavior in this case.

Choose a persistent storage location for your Frugal Manager. For example, /files/Frugal/FrugalManagerState.
Start a Frugal Manager on some machine, as with:

   [start] java -cp 
      /files/jini1_0/lib/jini-core.jar:
      /files/jini1_0/lib/jini-ext.jar:
      /files/jini1_0/lib/sun-util.jar:
      /files/jini1_0/lib/mahalo.jar:
      /files/jini1_0/lib/reggie.jar:
      /files/Frugal/FrugalManager.jar
   -Djava.rmi.server.codebase=http://yourname.com/Frugal/FrugalManager-dl.jar
   -Djava.security.manager=java.rmi.RMISecurityManager
   -Djava.security.policy=/files/Frugal/yourpolicy
   edu.jhu.cnds.Frugal.FrugalManagerServer
   [-f] /files/Frugal/FrugalManagerState [&]
   
   As before, use [start] on Windows machines, [-f] the first time 
   you use this Frugal Manager, and [&] on UNIX machines.

A Frugal Manager now appears on the local lookup service. The role of the Frugal Manager is to select the most appropriate compute engine for a metacomputer client. As long as most clients ask the Frugal Manager for a Frugal Resource rather than finding one on their own, the Manager acts to balance CPU and memory loads. It balances loads relative to the strength of the machines, so slow or low-memory machines do not become overloaded. After a short initialization period, the Frugal Manager is ready to perform this service.

Every 60 seconds, the Frugal Manager also tells the Frugal Resources the global metacomputer state. This includes a count of Frugal Resources in the metacomputer and the highest load that the metacomputer has seen. This information allows the Resources to accurately display their "cost" to a lookup browser user. This is a unitless numeric cost to the metacomputer to put a job on that machine. To the extent that that cost remains accurate in the 60 seconds between updates, the Frugal Manager will place a new job on the machine with the lowest cost. When that job increases that machine's load, that machine's cost increases.

Step 4: Lookup Browser

We have slightly modified the lookup browser from W. Keith Edwards' "Core Jini" to display Frugal Resource Beans on our test systems in a natural fashion. You can download this revised browser from the same location as the Frugal package. Run it with the appropriate variation on:

   [start] java -cp 
      /files/jini1_0/lib/jini-core.jar:
      /files/jini1_0/lib/jini-ext.jar:
      /files/jini1_0/lib/sun-util.jar:
      /files/Frugal/FrugalBrowser.jar:
      /files/Frugal/FrugalBrowser-dl.jar
   -Djava.rmi.server.codebase=http://yourname.com/Frugal/Browser-dl.jar
   -Djava.security.manager=java.rmi.RMISecurityManager
   -Djava.security.policy=/files/Frugal/yourpolicy
   edu.jhu.cnds.corejini.chapter9.Browser [&]

Once this is up and running, click on your local lookup service to display active services. Click on a Frugal Resource service to display its EntryBeans, including memory usage, CPU speed (as measured by our speed/load tester), and current cost.

Step 5: Sample Application

We have bundled a very simple application with this package. It locates a Frugal Manager, uses the Frugal Manager to find a compute engine, and then requests that that compute engine perform a job: computing the factorial of 20. Finally, it returns the answer. Optionally, start this application, as with:

   [start] java -cp
      /files/jini1_0/lib/jini-core.jar:
      /files/jini1_0/lib/jini-ext.jar:
      /files/jini1_0/lib/sun-util.jar:
      /files/Frugal/FrugalClient.jar
   -Djava.rmi.server.codebase=http://yourname.com/Frugal/FrugalClient.jar
   -Djava.security.manager=java.rmi.RMISecurityManager
   -Djava.security.policy=/files/Frugal/yourpolicy
   edu.jhu.cnds.FrugalTest.FrugalClient [&]

Step 6: Complex Sample Application

We have constructed a more complex sample application, which you may find in the FrugalDemo package.

Using the Package to Optimize your Computing Power

Finding a Frugal Manager

You can find a Frugal Manager by looking for the Class edu.jhu.cnds.Frugal.FrugalManager. Alternately, you can look for the Entry

new Name("FrugalManager")

This returns a Frugal Manager object if one is connected to the lookup service. It implements the interface FrugalManagerRemote.

For example:

   FrugalManagerRemote smartFinder = null;

   public void discovered(DiscoveryEvent evt) {

      ServiceRegistrar[] lookupRegistrars = evt.getRegistrars();
      Class[] desiredClass = new Class[1];

      try {
         desiredClass[0] = Class.forName("edu.jhu.cnds.Frugal.FrugalManager");
      } catch (ClassNotFoundException e) {
         System.err.println("Class not found.");
         System.exit(1);
      }

      Entry[] searchEntries = new Entry[] { new Name("FrugalManager") };
      ServiceTemplate searchDescription = 
          new ServiceTemplate(null, desiredClass, searchEntries);

      for (int i = 0; i < lookupRegistrars.length; i++) {
         System.out.println("Service found.");
         ServiceRegistrar singleRegistrar = lookupRegistrars[i];
         try {
            smartFinder = 
               (FrugalManagerRemote) singleRegistrar.lookup(searchDescription);
         } catch (java.rmi.RemoteException e) {
            e.printStackTrace();
            System.exit(2);
         }
      }
   }

Using the Frugal Manager to Find a Frugal Resource

The Frugal Manager interface specifies a key method:
public FrugalResourceRemote getFrugalResource().

This returns a Frugal Resource implementing the FrugalResourceRemote interface.

For example:

   FrugalResourceRemote computeEngine;

   [...]

   try {
      computeEngine = smartFinder.getFrugalResource();
   } catch (java.rmi.RemoteException e) {
      e.printStackTrace();
      System.exit(1);
   }

Using the Frugal Resource to Perform Work

The classes that perform work remotely must implement the Projectable interface. You can find this interface in the FrugalResource Jarfile. This interface specifies a Object[] main(Object[] argv) method. When you ship a Projectable class to a Frugal Resource, it runs this method with the arguments provided.

The Frugal Resource interface specifies the key compute engine method:
public Object[] run(Projectable submittedClass, Object argv[])

This runs the main routine of the submitted class, with argv[] as its input. For example:

   try {
      Object[] result = computeEngine.run((Projectable) (new workClass()),
         new Object[] {"Argument String", (int)2, new inputClass()});
   } catch (java.rmi.RemoteException e) {
      e.printStackTrace();
      System.exit(1);
   }

Applications Programming with the Frugal Package

The more you parallelize your Jini code, the greater the benefit you receive from the Frugal package. In particular, Frugal combines well with JavaSpaces-based distributed programming.

The FrugalEars class in FrugalUtilities.jar listens to discovery and remote events and maintains a reference to the local Frugal Manager(s). This is a Hashtable named FrugalManagers, containing ServiceItems. You can locate a Frugal Manager using this class or using the method above.

Here's how to initialize an "adjutant" FrugalEars class.

Class[] desiredClass = new Class[1];

   try {
      desiredClass[0] = Class.forName("edu.jhu.cnds.Frugal.FrugalManager");
   } catch (ClassNotFoundException e) {
      System.err.println("Frugal Class not found; check classpath.");
      System.exit(1);
   }

   Entry[] redundantParameter = new Entry[] { new Name("FrugalManager") };

   adjutant.searchDescription = 
      new ServiceTemplate(null, desiredClass, redundantParameter);

   try {
      adjutant.scout = 
         new LookupDiscoveryManager(new String[] { "", "Frugal" }, null, null);
   } catch (Exception e) {
      System.out.println("Couldn't send out a discovery.\n");
      System.err.println(e.toString());
      System.exit(1);
   }

   adjutant.scout.addDiscoveryListener(adjutant);

"JavaSpaces(TM) Principles, Patterns, and Practice" describes generic workers, that pull a small amount of work from a JavaSpace, perform the work, and return the results to the space. These workers can be chained together to perform complex distributed applications. Instead of running the task's execute routine, build the task as a Projectable class and run it with:

   machineFinder = adjutant.getManager();

   if (machineFinder != null)
      computeServer = machineFinder.getFrugalResource();

   Object[] args = new Object[1];
   args[0] = space;

   Object[] result = computeServer.run((Projectable) task, args);
   if (result != null)
	entryResult = (Entry) result[0];