Modeling the cost of resource allocation in distributed control

ABSTRACT

Modifying our previously developed simulation model [FRA89], we study in this paper the costs associated with distributed allocation of computing resources in a multitasking environment. Using funds endowed upon arrival, computing tasks compete for necessary resources through sealed-bid auctions to improve their processing schedules. The costs and times dedicated to auctioning are compared to the costs and times allowed for task processing. Measuring computing resources in terms of processing rates allows the task management, in the form of an auction, algorithm, to have its requirements specified in the same way as the requirements for the simulated mission processing. Machine capacity is computed for and assigned to each completing task. Data are then compiled by segmented capacity classes. A unifying theme of past and current research is the efficiency of auctioning to allocate reconfigurable computing resources in a variable capacity machine. We observed that at optimal rates of occurrence of capacity classes which minimize the total costs per successful completion, congestion was resolved through auctions generating endogenously implied prices which substantially exceeded the exogenously imposed price.

REFERENCES

• FRA87: Martin D. Fraser , Ross A. Gagliano, Mathematical modeling and Ada simulation of some synchronization processes, Proceedings of the 20th annual symposium on Simulation, p.163-184, June 1987, Tampa, Florida, United States
• FRA89: Martin D. Fraser , Ross A. Gagliano, The simulation of a distributed control model for resource allocation and the implied pricing, Proceedings of the 22nd annual symposium on Simulation, p.81-92, March 1989, Tampa, Florida, United States
• GAG88: Ross A. Gagliano , Martin D. Fraser , Mark E. Schaefer, Simulation of a market model for distributed control, Proceedings of the 21st annual symposium on Simulation, p.171-187, January 1988, Tampa, Florida, United States
• GAG87: Gagliano, R. A., M. D. Fraser, and M. E. Schaefer. 1987. "A Market Model for Distributed Control: The Role of Algorithms for the Initial Endowment of Wealth," to appear in the Proceedings of the 4th International Symposium on Systems Research, Informatics and Cybernetics, The International Institute for Advanced Studies in Systems Research and Cybernetics.
• GAG90: Gagliano, R. A. and M. E. Schaefer. 1990. "Decentralized Control of Access to Resources in a Network: Interdependence of Strategies in a Challenge Ring Model," (in press) Advances i__nnControl Networks and Large Scale Parallel Distributed Processing Models, M. D. Fraser (ed.), Ablex Publishing Co.
• HOC81: R. W. Hockney , C. R. Jesshope, Parallel Computers Two: Architecture, Programming and Algorithms, IOP Publishing Ltd., Bristol, UK, 1988
• MEN85: Haim Mendelson, Pricing computer services: queueing effects, Communications of the ACM, v.28 n.3, p.312-321, March 1985 [doi>10.1145/3166.3171]
• RAI86: M R Railey, Dynamic control structures for cooperating processes, University of Illinois, Department of Computer Science, Urbana, IL, 1986
• RAS87: Rashid, R. F. 1987. "Designs for Parallel Architectures," UNIX Review, Vol. 5, No. 4, April.
• WHI89: Martin D. Fraser , Ross A. Gagliano, The simulation of a distributed control model for resource allocation and the implied pricing, Proceedings of the 22nd annual symposium on Simulation, p.81-92, March 1989, Tampa, Florida, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Types of simulation (continuous and discrete)*

General Terms:
Algorithms, Design, Management, Performance