Decentralized Optimal Power Pricing on the CM-5
Steven Lumetta
(Professor D. E. Culler)
(NSF) CDA-87-22788 and NSF Graduate Fellowship

Before massively parallel systems can find their way into general use,
language and tool designers must recognize that neither easy
modification nor high-speed execution is alone adequate to meet the
needs of program development. To establish an environment in which
useful parallel software development can occur, it is necessary not
only to have a reasonably flexible and functional language in which to
program, but also to maintain the execution time decrease which
originally necessitates use of a parallel machine.

We have developed a small package to support synchronization of
fine-grained objects on the CM-5.  The package runs atop CM Active
Messages (CMAM) [1], providing a simple and efficient interface
through which the programmer can manipulate small objects. We hope
eventually to make this object system available within the Split-C [2]
library.

In cooperation with our peers in Electrical Engineering, we have
implemented and developed an algorithm for the optimal distribution of
electrical power discussed in [3]. Given a radial power distribution
tree with lossy wires, the algorithm uses local constraint and benefit
information to calculate the power demands for each customer. By
iteratively adjusting the prices and recalculating the commands in a
decentralized fashion, it is possible to reach a set of power demands
which are globally optimal (i.e., have the maximum benefit to the
community as a whole).

Not only does this application have potential utility in many
countries around the world, but the development process we underwent
demonstrates that it is possible to strike a balance between ease of
use and efficiency when programming parallel machines. We claim that
such a balance is critical to the eventual acceptance of parallel
platforms for the development of software.

[1] T. von Eicken, D. E. Culler, S. C. Goldstein, K. E. Schauser,
Active Messages: A Mechanism for Integrated Communication and
Computation,UC Berkeley Computer Science Division, Report No. UCB/CSD
92/675, March 1992.

[2] D. E. Culler, A. Dusseau, S. C. Goldstein, A. Krishnamurthy, S.
Lumetta, T. von Eicken, and K. Yelick, "Parallel Programming in
Split-C," Proc. Supercomputing, 1993.

[3] L. Murphy, R. J. Kaye, and F. F. Wu, "Distributed Spot Pricing in
Radial Distribution Systems," Paper 93 WM 148-7 PWRS, IEEE Power
Engineering Soc. Winter Mtg., Columbus, OH, February 1993.