A heterogeneous multiprocessor design and the distributed scheduling of its task group workload

ABSTRACT

A multiprocessor architecture is proposed which is based on the Multics concept of having all on-line information processor-addressible. All memory management is done by an intelligent paged virtual memory system, and each processor deals only with those segments relevant to its single executing program. The processors are chosen to have different implementations of a single system-wide instruction set and the problem is to effectively schedule different categories of programs, called task groups, on the dissimilar processors. Average weighted instruction times for each task group on every processor are defined as task/processor suitability measures, and typical values are given for different groups of programs running on IBM 370 models. Through the use of linear programming techniques, an optimal schedule for any such multiprocessor is then defined for the static case where task group loads and task/processor suitability values are known in advance. A priority-based task management scheduling algorithm is then defined which uses the optimal schedule of the formal model as a parameter, and its performance is simulated.

REFERENCES

• 1: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 2: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 3: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 4: Coffman, E. G. Jr., ed., Computer and Job Shop Scheduling Theory, Wiley Interscience, 1976.
• 5: Frieder, G. and Brenner, M., "Distribution of instruction usage in different application categories," Nanodata Corp, Buffalo, N.Y., Internal Data 1978.
• 6: Kleinrock, L., "A continuum of time-sharing scheduling algorithms." Proc. AFIPS 1970 Southern Computer Conf., Vol. 36, AFIPS Press, Montvale, N.J., 1970, 453-458.
• 7: E. L. Lawler , J. Labetoulle, On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming, Journal of the ACM (JACM), v.25 n.4, p.612-619, Oct. 1978 [doi>10.1145/322092.322101]
• 8: Lester, E., "The investigation of service time distributions." Tech. Rep. CSRG-25, University of Toronto, Ontario, Canada, 1973
• 9: Miller, L. J., "Optimal scheduling of task groups on a tightly coupled multiprocessor." Tech. Rep., SUNY, Buffalo, N.Y., Feb. 1979.
• 10: Muntz, R. R., "Scheduling and Resource Allocation in Computer Systems." Software Systems Principles: A Survey (P. Freeman, ed.), Science Research Associates, 1975, 269-304
• 11: Noguchi, K., Ohnishi, I., and Morita, H., "Design considerations for a heterogeneous tightly-coupled multiprocessor system." Proc. AFIPS 1975 National Computer Conference., Vol. 44, AFIPS Press, Montvale, N.J., 1975, 561-565.
• 12: Kenneth J. Omahen, Capacity Bounds for Multiresource Queues, Journal of the ACM (JACM), v.24 n.4, p.646-663, Oct. 1977 [doi>10.1145/322033.322043]
• 13: Elliott I. Organick, The Multics System: An Examination of Its Structure, The MIT Press, 1972
• 14: Richter, L., and Zehn, A., "TARCUS A modularized system approach." Proceedings Sixth Texas Conference on Computer Systems, Austin, Texas, 1977
• 15: Silberman, G., "Delayed staging storage heirarchies and the active memory concept", Ph.D. Thesis, SUNY Buffalo, N.Y., July 1980.
• 16: Schneider, P., "Heirarchically arranged memory system for a data processing arrangement having virtual addressing", U.S. Patent # 4130870, Dec. 1978.
• 17: Wilner, W. T., "Burroughs B1700 memory utilization." Proceedings AFIPS 1972 Fall Joint Computer Conference, Vol. 41A, AFIPS Press, Montvale, N.J., 1972, 579-586.
• 18: Thornton, J. E., "Back-End Network Approaches," Computer, 13, 2 (Feb. 1980), 10-17.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Heterogeneous (hybrid) systems

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

General Terms:
Algorithms, Design