A recently published algorithm shows how to assign modules to a two-processor computer system with distributed execution so as to minimize the total of execution costs and interprocessor communication costs. In this paper we consider the same problem except that one processor has limited memory capacity. Although this problem is NP-complete, techniques based on the Gomory–Hu tree from network flow theory can be applied to instances of the problem to obtain a reduction in complexity. A new technique based on a graph called the inclusive cut graph is shown to be an even more powerful tool. These two techniques can solve some instances of the problem completely; still others are reduced sufficiently to be susceptible to enumerative techniques. In the worst case, the techniques yield no reduction in problem size.

Using the Independent Reference assumption to model program behavior, the performance of different buffer organizations (Fully Associative, Direct Mapping, Set Associative.and Sector) are analyzed' (1)The expressions for their fault rate are derived To show more explicitly the dependence of the fault rate on the factors that affect it, distribution-free upper bounds on fault rates are computed for the Direct Mapping, Set Associative, and Sector buffers The use of such bounds is illustrated in the case of the Direct Mapping buffer (2) The performance of the buffers for FIFO and Random Replacement are shown to be identical (3) It is possible to restructure programs to take advantage of the basic organization of the buffers The effect of such restructuring is quantified for the Direct Mapping buffer It is shown that the performance of the Direct Mapping buffer under near-optimal restructuring is comparable to the performance of the Fully Associative buffer Further, the effect of this restructuring is shown to be potentially stronger than that of buffer replacement algorithms KEY WORDS AND PHRASES buffer, cache, statistical analysis, performance analysis, program behavior models, paging, page replacement algorithms, program restructuring, fault rate, distribution-free bounds CR CATEGORIES 4 35, 5 42, 6 34, 8 3 General permission to make fair use in teaching or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that repnntmg privileges were granted by permission of the AssoclaUon for Computmg Machinery.To otherwise repnnt a figure, table, other substantial excerpt, or the entire work requires specific permission as does republication, or systematic or multiple reproduction This research was supported by a f¢llowsMp from the Ministry of Education, Government of India, and by the Joint Service Electronics Project Contract N00014-75-C-0601 Computer tune was provided by the Energy

A complicated expression for the average number of active modules, in a published model for interleaved memory, is shown to be a function well studied in other contexts.

The logical design of an adder-subtracter for negative binary numbers is described. The twin-carry generates during the addition, is converted into a single hybrid-carry-borrow, this helps to design a circuit which can function as an adder or a subtracter with a simple switching control.

The logical design of a polarizer for negative binary numbers is described and compared with the two's complementer used for positive binary numbers.