Research and Advances

Anaysis of interleaved memory systems using blockage buffers

A model of interleaved memory systems is presented, and the analysis of the model by Monte Carlo simulation is discussed. The simulations investigate the performance of various system structures, i.e. schemes for sending instruction and data requests to the memory system. Performance is measured by determining the distribution of the number of memory modules in operation during a memory cycle. An important observation from these investigations is that separately grouping instruction and data requests for memory can substantially increase the average number of memory modules in operation during a memory cycle. Results of the simulations and an analytical study are displayed for various system structures.


Author Archives

Research and Advances

Scheduling independent tasks to reduce mean finishing time

Sequencing to minimize mean finishing time (or mean time in system) is not only desirable to the user, but it also tends to minimize at each point in time the storage required to hold incomplete tasks. In this paper a deterministic model of independent tasks is introduced and new results are derived which extend and generalize the algorithms known for minimizing mean finishing time. In addition to presenting and analyzing new algorithms it is shown that the most general mean-finishing-time problem for independent tasks is polynomial complete, and hence unlikely to admit of a non-enumerative solution.
Research and Advances

A study of storage partitioning using a mathematical model of locality

Both fixed and dynamic storage partitioning procedures are examined for use in multiprogramming systems. The storage requirement of programs is modeled as a stationary Gaussian process. Experiments justifying this model are described. By means of this model dynamic storage partitioning is shown to provide substantial increases in storage utilization and operating efficiency over fixed partitioning.
Research and Advances

File structures using hashing functions

A general method of file structuring is proposed which uses a hashing function to define tree structure. Two types of such trees are examined, and their relation to trees studied in the past is explained. Results for the probability distributions of path lengths are derived and illustrated.
Research and Advances

Organizing matrices and matrix operations for paged memory systems

Matrix representations and operations are examined for the purpose of minimizing the page faulting occurring in a paged memory system. It is shown that carefully designed matrix algorithms can lead to enormous savings in the number of page faults occurring when only a small part of the total matrix can be in main memory at one time. Examination of addition, multiplication, and inversion algorithms shows that a partitioned matrix representation (i.e. one submatrix or partition per page) in most cases induced fewer page faults than a row-by-row representation. The number of page-pulls required by these matrix manipulation algorithms is also studied as a function of the number of pages of main memory available to the algorithm.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved