Overview   Package  Class  Tree  Deprecated  Index  Help 
 PREV PACKAGE   NEXT PACKAGE FRAMES    NO FRAMES

Package edu.jhu.cnds.Frugal

The Frugal package allows jobs to choose intelligently among the compute engines registered with a Jini lookup service.

See:
          Description

Interface Summary
FrugalManager General interface for a Frugal Manager, capable of finding a suitable Frugal Resource and returning it to the caller.
FrugalManagerRemote Remote, administrable version of the Frugal Manager interface.
FrugalResource General interface for a Frugal Resource, capable of performing work for the caller.
FrugalResourceRemote Remote, administrable version of the Frugal Resource interface.
FrugalService General interface for a Frugal Manager or Resource server, responsible for registering the Manager or Resource service with lookup services.
FrugalServiceRemote Remote version of the Frugal Service interface.
Projectable General interface for classes that can be executed remotely by Frugal Resource services.
 

Class Summary
Administrator A class for handling common administrative chores.
Derived from the BasicUnicastAdmin class by W Keith Edwards.
Cost An entry corresponding to a given Frugal Resource's cost.
CostBean An entry bean class corresponding to Frugal Cost entries.
Inspired by CapacityBean of "Core Jini," by W Keith Edwards.
CPUSpeed An entry corresponding to a given Frugal Resource's speed.
CPUSpeedBean An entry bean class corresponding to CPU Speed entries.
Inspired by CapacityBean of "Core Jini," by W Keith Edwards.
FrugalEars An event handling class for users of the Frugal Package.
FrugalID An entry corresponding to a given Frugal Resource's ID.
FrugalIDBean An entry bean class corresponding to Frugal ID entries.
Inspired by CapacityBean of "Core Jini," by W Keith Edwards.
FrugalManagerEars An event handling class for Frugal Managers.
FrugalManagerImpl Concrete implementation of a Frugal Manager, capable of finding a suitable Frugal Resource and returning it to the caller.
FrugalManagerServer A server class, designed to register Frugal Manager implementations with lookup services.
FrugalResourceImpl Concrete implementation of a Frugal Resource, capable of performing work for the caller.
FrugalResourceServer A server class, designed to register Frugal Resource implementations with lookup services.
LoadTester A load testing application, capable of abstractly measuring a system's load and speed.
Memory An entry corresponding to a given Frugal Resource's memory.
MemoryBean An entry bean class corresponding to CPU Memory entries.
Inspired by CapacityBean of "Core Jini," by W Keith Edwards.
NameBean An entry bean class corresponding to Name entries.
Inspired by CapacityBean of "Core Jini," by W Keith Edwards.
 

Package edu.jhu.cnds.Frugal Description

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:

More importantly, however, it has the following benefit:

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

Step 2: Compute Engines

   [start] java -cp 
      /files/jini1_1/lib/jini-core.jar:
      /files/jini1_1/lib/jini-ext.jar:
      /files/jini1_1/lib/sun-util.jar:
      /files/Frugal/FrugalResource.jar
   -Xms32m -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.  The memory size defined
   by -Xms and -Xmx (in this case, 32 Megs) is the memory available 
   to the Frugal virtual machine.
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.

   [start] java -cp 
      /files/jini1_1/lib/jini-core.jar:
      /files/jini1_1/lib/jini-ext.jar:
      /files/jini1_1/lib/sun-util.jar:
      /files/jini1_1/lib/mahalo.jar:
      /files/jini1_1/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 virtual 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.

The Frugal Manager logs events to stderr, including client requests for Frugal Resources and information on updates from the Jini lookup service. These updates are frequent.

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. This package is not a part of the Frugal System and we make it available only as a convenience. Run it with the appropriate variation on:

   [start] java -cp 
      /files/jini1_1/lib/jini-core.jar:
      /files/jini1_1/lib/jini-ext.jar:
      /files/jini1_1/lib/sun-util.jar:
      /files/Frugal/FrugalBrowser.jar:
      /files/Frugal/FrugalBrowser-dl.jar
   -Djava.rmi.server.codebase=http://yourname.com/Frugal/FrugalBrowser-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_1/lib/jini-core.jar:
      /files/jini1_1/lib/jini-ext.jar:
      /files/jini1_1/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];
   }

Author: R. Sean Borgstrom
Version: 2.0

License for Client Code

The following classes in this package fall under the client license:
The client license follows:

Copyright (c) 2000, The Johns Hopkins University
All rights reserved.

Redistribution and use in source and binary forms, with or without 
modification, are permitted provided that the following conditions 
are met:

* Redistributions of source code must retain the above copyright 
notice, this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright 
notice, this list of conditions and the following disclaimer in the 
documentation and/or other materials provided with the distribution.
* Neither the name of the Johns Hopkins University nor the names of 
this product's contributors may be used to endorse or promote 
products derived from this software without specific prior written 
permission.
* The Frugal System's development was partially funded by a grant from 
the Defense Advance Research Projects Agency (DARPA) to Johns Hopkins 
University. The U.S. Government retains certain rights in this software.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT 
NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

License for the Server Code

All other classes in this package fall under the server license, including the following:
The server license follows:

Copyright (c) 2000, The Johns Hopkins University
All rights reserved.

Redistribution and use in source and binary forms, with or 
without modification, are permitted provided that the 
following conditions are met:

* Redistributions of source code must retain the above 
copyright notice, this list of conditions and the following 
disclaimer.
* Redistributions in binary form must reproduce the above 
copyright notice, this list of conditions and the following 
disclaimer in the documentation and/or other materials 
provided with the distribution.
* Redistributions in source or binary form must include some 
form of documentation. That documentation must include a
chapter, section, or appendix entitled 
"The Frugal System (version 2.0)" and that chapter, section, 
or appendix must include the text of Exhibit A below in its 
entirety.
* Neither the name of the Johns Hopkins University nor the 
names of this product's contributors may be used to endorse 
or promote products derived from this software without 
specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, 
BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY 
AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT 
SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 
BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Exhibit A
The Frugal System

The Frugal System is a "metacomputing" system for intelligently 
using the computational resources of a network of machines 
connected with Jini technology. Normally, a computational 
task runs on the machine where a user or administrator starts 
its execution. However, the more programs a single machine 
runs, the greater its load, and the greater the risk that 
machine will run out of memory and begin thrashing. The Frugal 
System allows tasks to run, instead, on a machine carefully 
chosen to maximize the average job performance over all the 
jobs on the system.

The Frugal System has two major components. Running a "Frugal Resource" 
allows a machine to perform computation for other machines on 
the network. Other programs contact the "Frugal Manager" to find out 
which Frugal Resource to use. For example, a user program wishing to 
run a large simulation might contact the Frugal Manager. The 
Frugal Manager returns a reference to an appropriate Frugal 
Resource. The user program has the Frugal Resource perform the 
simulation and return its results.

The strategy used by the Frugal Manager to place tasks has provably 
good theoretical properties. Its performance competes (within 
certain limits) with the best possible algorithm, even if that 
algorithm knows the future. In addition, the Center for Networking 
and Distributed Systems at the Johns Hopkins University has 
extensively tested this strategy, demonstrating its practical 
effectiveness compared to standard strategies.

The Frugal System was developed in 2000 by R. Sean Borgstrom as part
of the doctoral dissertation "A Cost-Benefit Approach to Resource 
Allocation in Scalable Metacomputers", with Dr. Yair Amir acting as
advisor, at the Center for Networking and Distributed Systems at 
the Johns Hopkins University. For more information about the 
Frugal System and active research on metacomputing systems, see 
http://www.cnds.jhu.edu/projects/metacomputing. For the Frugal System 
(version 2.0), see http://www.cnds.jhu.edu/projects/metacomputing/frugal.

The Frugal System's development was partially funded by a grant from 
the Defense Advance Research Projects Agency (DARPA) to Johns Hopkins 
University. The U.S. Government retains certain rights in this software.

Overview   Package  Class  Tree  Deprecated  Index  Help 
 PREV PACKAGE   NEXT PACKAGE FRAMES    NO FRAMES