Explicit parallel processing description and control in programs for multi- and uni-processor computers

ABSTRACT

This paper discusses the development and current state of the art in parallel processing. The advantages and disadvantages of the various approaches are described from a pragmatic viewpoint. One that is described and discussed is a natural extension of the evolutionary approaches. This alternative covers the problems of locating, describing, controlling, and scheduling parallel processing. It is a general-purpose approach that is applicable to all types of data processing and computer configuration.

REFERENCES

• 1: G. M. Amdahl, "New Concepts In Computing System Design," Proc. IRE, vol. 50, (May 1962) pp. 1073--1077.
• 2: James P. Anderson, Program structures for parallel processing, Communications of the ACM, v.8 n.12, p.786-788, Dec. 1965 [doi>10.1145/365691.365945]
• 3: James P. Anderson , Samuel A. Hoffman , Joseph Shifman , Robert J. Williams, D825 - a multiple-computer system for command & control, Proceedings of the December 4-6, 1962, fall joint computer conference, p.86-96, December 04-06, 1962, Philadelphia, Pennsylvania [doi>10.1145/1461518.1461527]
• 4: J. R. Ball , R. C. Bollinger , T. A. Jeeves , R. C. McReynolds , D. H. Shaffer, On the use of the SOLOMON parallel-processing computer, Proceedings of the December 4-6, 1962, fall joint computer conference, p.137-146, December 04-06, 1962, Philadelphia, Pennsylvania [doi>10.1145/1461518.1461532]
• 5: Gerald P. Bergin, Method of control for re-entrant programs, Proceedings of the October 27-29, 1964, fall joint computer conference, part I, October 27-29, 1964, San Francisco, California [doi>10.1145/1464052.1464057]
• 6: J. McCarthy , S. Boilen , E. Fredkin , J. C. R. Licklider, A time-sharing debugging system for a small computer, Proceedings of the May 21-23, 1963, spring joint computer conference, May 21-23, 1963, Detroit, Michigan [doi>10.1145/1461551.1461559]
• 7: F. P. Brooks, Jr., "The Future of Computer Architecture," Proc. IFIP, volume 1, 1965, p. 87.
• 8: E. Bryan, "The Dynamic Characteristics of Computer Programs," Rand Corporation, 1964 (Paper to SHARE XXII).
• 9: Werner Buchholz, Planning a computer system: Project Stretch, McGraw-Hill, Inc., Hightstown, NJ, 1962
• 10: A. W. Burks, The Logic of Fixed and Growing Automata, University of Michigan, Eng. Res. Inst., Ann Arbor, 1957.
• 11: Wei Chang , Donald J. Wong, Analysis of Real Time Multiprogramming, Journal of the ACM (JACM), v.12 n.4, p.581-588, Oct. 1965 [doi>10.1145/321296.321309]
• 12: T. E. Cheatham and G. F. Leonard, "An Introduction to the CL-II Programming System," Computer Associates-63-7-SD, November 1963.
• 13: E. F. Codd, "Multiprogram Scheduling," CACM, (June & July 1963) pp. 347 and 413.
• 14: E. F. Codd , E. S. Lowry , E. McDonough , C. A. Scalzi, Multiprogramming STRETCH: feasibility considerations, Communications of the ACM, v.2 n.11, p.13-17, Nov. 1959 [doi>10.1145/368481.368502]
• 15: E. G. Coffman, Jr., et al, "A General-Purpose Time-Sharing System," AFIPS, volume 25, Proc. SJCC, Spartan Books, Washington, D.C., 1964.
• 16: M. Phyllis Cole , Philip H. Dorn , C. Richard Lewis, Operational software in a disk oriented system, Proceedings of the October 27-29, 1964, fall joint computer conference, part I, October 27-29, 1964, San Francisco, California [doi>10.1145/1464052.1464083]
• 17: Melvin E. Conway, A multiprocessor system design, Proceedings of the November 12-14, 1963, fall joint computer conference, November 12-14, 1963, Las Vegas, Nevada [doi>10.1145/1463822.1463838]
• 18: Melvin E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, v.6 n.7, p.396-408, July 1963 [doi>10.1145/366663.366704]
• 19: Fernando J. Corbató , Marjorie Merwin-Daggett , Robert C. Daley, An experimental time-sharing system, Proceedings of the May 1-3, 1962, spring joint computer conference, May 01-03, 1962, San Francisco, California [doi>10.1145/1460833.1460871]
• 20: Jack B. Dennis, Segmentation and the Design of Multiprogrammed Computer Systems, Journal of the ACM (JACM), v.12 n.4, p.589-602, Oct. 1965 [doi>10.1145/321296.321310]
• 21: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 22: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 23: Phillippe Dreyfuss, System design of the Gamma 60, Proceedings of the May 6-8, 1958, western joint computer conference: contrasts in computers, May 06-08, 1958, Los Angeles, California [doi>10.1145/1457769.1457805]
• 24: S. Fernback, "Computers in the USA---Today and Tomorrow," Proc. IFIP, vol. 1, 1965, p. 77.
• 25: Donald R. Fitzwater , Earl J. Schweppe, Consequent procedures in conventional computers, Proceedings of the October 27-29, 1964, fall joint computer conference, part I, October 27-29, 1964, San Francisco, California [doi>10.1145/1464052.1464094]
• 26: S. Gill, "Parallel Programming," Computer Journal, vol. 1, (1958) p. 2.
• 27: A. C. D. Haley, The KDF.9 computer system, Proceedings of the December 4-6, 1962, fall joint computer conference, p.108-120, December 04-06, 1962, Philadelphia, Pennsylvania [doi>10.1145/1461518.1461529]
• 28: John Holland, A universal computer capable of executing an arbitrary number of sub-programs simultaneously, Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference, p.108-113, December 01-03, 1959, Boston, Massachusetts [doi>10.1145/1460299.1460311]
• 29: John H. Holland, Iterative circuit computers, Papers presented at the May 3-5, 1960, western joint IRE-AIEE-ACM computer conference, May 03-05, 1960, San Francisco, California [doi>10.1145/1460361.1460397]
• 30: T. J. Howarth, et al, "The Manchester University Atlas Operating System, Part II: User's Description," Computer Journal, vol. 4, (1961) p. 226.
• 31: D. J. Howarth , P. D. Jones , M. T. Wyld, The Atlas scheduling system, Proceedings of the May 21-23, 1963, spring joint computer conference, May 21-23, 1963, Detroit, Michigan [doi>10.1145/1461551.1461560]
• 32: E. T. Irons, A rapid turnaround multi-programming system, Communications of the ACM, v.8 n.3, p.152-157, March 1965 [doi>10.1145/363791.363803]
• 33: T. Kilburn, et al, "The Manchester University Atlas Operating System, Part I: Internal Organization," Computer Journal, vol. 4, (1961) p. 222.
• 34: T. Kilburn , R. B. Payne , D. J. Howarth, The Atlas supervisor, Proceedings of the December 12-14, 1961, eastern joint computer conference: computers - key to total systems control, p.279-294, December 12-14, 1961, Washington, D.C. [doi>10.1145/1460764.1460786]
• 35: Donald E. Knuth, Additional comments on a problem in concurrent programming control, Communications of the ACM, v.9 n.5, p.321-322, May 1966 [doi>10.1145/355592.365595]
• 36: Norman Landis , Andrew Manos , L. Richard Turner, Initial experience with an operating multiprogramming system, Communications of the ACM, v.5 n.5, p.282-286, May 1962 [doi>10.1145/367710.367754]
• 37: A. L. Leiner, et al, "Concurrently Operating Computer Systems," ICIP, 1959, B. 12. 17. pp. 353--361.
• 38: A. L. Leiner , W. A. Notz , J. L. Smith , A. Weinberger, Organizing a network of computers to meet deadlines, Papers and discussions presented at the December 9-13, 1957, eastern joint computer conference: Computers with deadlines to meet, p.115-128, December 09-13, 1957, Washington, D.C. [doi>10.1145/1457720.1457742]
• 39: G. F. Leonard , J. R. Goodroe, An environment for an operating system, Proceedings of the 1964 19th ACM national conference, p.52.301-52.3011, January 1964 [doi>10.1145/800257.808910]
• 40: M. J. Marcotty , F. M. Longstaff , Audrey P. M. Williams, Time-sharing on the Ferranti-Packard FP6000 computer system, Proceedings of the May 21-23, 1963, spring joint computer conference, May 21-23, 1963, Detroit, Michigan [doi>10.1145/1461551.1461557]
• 41: J. L. McKenney, "Simultaneous Processing of Jobs on an Electronic Computer," Management Sci. vol. 8, (April, 1962) pp. 344--54.
• 42: M. R. Mills, "Operational Experience of Time Sharing and Parallel Processing," Computer Journal, vol. 6, (1963) p. 28.
• 43: M. R. Nekora, Comment on a paper on parallel processing, Communications of the ACM, v.4 n.2, p.103, Feb. 1961 [doi>10.1145/366105.366139]
• 44: J. Nievergelt, Parallel methods for integrating ordinary differential equations, Communications of the ACM, v.7 n.12, p.731-733, Dec. 1964 [doi>10.1145/355588.365137]
• 45: Ascher Opler, Procedure-oriented language statements to facilitate parallel processing, Communications of the ACM, v.8 n.5, p.306-307, May 1965 [doi>10.1145/364914.364947]
• 46: G. E. Pickering , E. G. Mutschler , G. A. Erickson, Multicomputer programming for a large scale real-time data processing system, Proceedings of the April 21-23, 1964, spring joint computer conference, April 21-23, 1964, Washington, D.C. [doi>10.1145/1464122.1464166]
• 47: R. E. Porter, (Title unknown) Parallel Programming Conference, May 1960.
• 48: Jeanne Poyen, Private discussion with Opler, 1959.
• 49: George Radin , H. Paul Rogoway, NPL: highlights of a new programming language, Communications of the ACM, v.8 n.1, p.9-17, Jan. 1965 [doi>10.1145/363707.363708]
• 50: Arthur M. Rosenberg, Computer-usage accounting for generalized time-sharing systems, Communications of the ACM, v.7 n.5, p.304-308, May 1964 [doi>10.1145/364099.364332]
• 51: W. F. Schmitt and A. B. Tonik, "Sympathetically Programmed Computers," ICIP, 1959, pp. 344--348.
• 52: Eugene S. Schwartz, An Automatic Sequencing Procedure with Application to Parallel Programming, Journal of the ACM (JACM), v.8 n.4, p.513-537, Oct. 1961 [doi>10.1145/321088.321093]
• 53: A. B. Shafritz , A. E. Miller , K. Rose, Multi-level programming for a real-time system, Proceedings of the December 12-14, 1961, eastern joint computer conference: computers - key to total systems control, p.1-16, December 12-14, 1961, Washington, D.C. [doi>10.1145/1460764.1460765]
• 54: Daniel L. Slotnick , W. Carl Borck , Robert C. McReynolds, The SOLOMON computer, Proceedings of the December 4-6, 1962, fall joint computer conference, p.97-107, December 04-06, 1962, Philadelphia, Pennsylvania [doi>10.1145/1461518.1461528]
• 55: Jon S. Squire , Sandra M. Palais, Programming and design considerations of a highly parallel computer, Proceedings of the May 21-23, 1963, spring joint computer conference, May 21-23, 1963, Detroit, Michigan [doi>10.1145/1461551.1461597]
• 56: E. Strachey, "Time-Sharing in Large Fast Computers," ICIP, 1959, p. 336 and Computers & Automation, (Aug. 1959).
• 57: Rankin N. Thompson , John A. Wilkinson, The D825 automatic operating and scheduling program, Proceedings of the May 21-23, 1963, spring joint computer conference, May 21-23, 1963, Detroit, Michigan [doi>10.1145/1461551.1461558]
• 58: Niklaus Wirth, A note on “Program structures for parallel processing”, Communications of the ACM, v.9 n.5, p.320-321, May 1966 [doi>10.1145/355592.365594]
• 59: Lynn D. Yarbrough, Some thoughts on parallel processing, Communications of the ACM, v.3 n.10, p.539, Oct. 1960 [doi>10.1145/367415.367426]