We collect and analyze a snapshot of data from 10,568 file systems of 4801 Windows personal computers in a commercial environment. The file systems contain 140 million files totaling 10.5 TB of data. We develop analyt...
详细信息
We collect and analyze a snapshot of data from 10,568 file systems of 4801 Windows personal computers in a commercial environment. The file systems contain 140 million files totaling 10.5 TB of data. We develop analytical approximations for distributions of file size, file age, file functional lifetime, directory size, and directory depth, and we compare them to previously derived distributions. We find that file and directory sizes are fairly consistent across file systems, but file lifetimes vary widely and are significantly affected by the job function of the user. Larger files tend to be composed of blocks sized in powers of two, which noticeably affects their size distribution. File-name extensions are strongly correlated with file sizes, and extension popularity varies with user job function. On average, file systems are only half full.
The authors propose a taxonomy of parallel sorting that encompasses a broad range of array- and file-sorting algorithms. They analyze how research on parallel sorting has evolved, from the earliest sorting networks to...
详细信息
The authors propose a taxonomy of parallel sorting that encompasses a broad range of array- and file-sorting algorithms. They analyze how research on parallel sorting has evolved, from the earliest sorting networks to shared memory algorithms and VLSI sorters. In the context of sorting networks, the authors describe two fundamental parallel merging schemes: the odd-even and the bitonic merge. They discuss sorting algorithms that evolved from these merging schemes for parallel computers, whose processors communicate through interconnection networks such as the perfect shuffle, the mesh, and a number of other sparse networks. They describe how faster algorithms have been derived from parallel enumeration sorting schemes, where, with a shared memory model of parallel computation, keys are first ranked and then rearranged according to their rank. Parallel sorting algorithms are evaluated according to several criteria related to both the time complexity of an algorithm and its feasibility from the viewpoint of computer architecture.
The paper describes completed work in applying dynamic testing and static analysis to the concurrent process software. The techniques were used in the program of creating an environment conducive to the production and...
详细信息
The paper describes completed work in applying dynamic testing and static analysis to the concurrent process software. The techniques were used in the program of creating an environment conducive to the production and testing of concurrent-process flight software.
A new scheduling algorithm is described for a multicomputer connected in a point-to-point fashion. The algorithm is both distributed (every processor runs the same algorithm) and stable (collective load balancing deci...
详细信息
A new scheduling algorithm is described for a multicomputer connected in a point-to-point fashion. The algorithm is both distributed (every processor runs the same algorithm) and stable (collective load balancing decisions will not cause unnecessary overloading of a processor in the network). It is assumed that process execution times are not known in advance and that inter-processor transfer times are non-trivial. Load is balanced by migrating suitable jobs after they have been run long enough to obtain an estimate of their required service time. The algorithm is suitable for job scheduling in a distributed time-sharing system implemented on a multicomputer. Performance of the algorithm is investigated through simulation.
A description is given of the KRTM kernel which has been designed in order to facilitiate real-time multiprogramming during the development of TELEX-M, a dedicated operating system for telex exchanges. KRTM creates a ...
详细信息
A description is given of the KRTM kernel which has been designed in order to facilitiate real-time multiprogramming during the development of TELEX-M, a dedicated operating system for telex exchanges. KRTM creates a run-time environment supporting execution of all the operating system programs. Although the KRTM characteristics have been derived from the very concrete real life program (to design and implement a reliable operating system capable to provide a satisfactory service for 512 telex abonents and trunks to other switching systems), the resulting product seems to be more general, covering a wider class of strongly multiprogramed, real-time minicomputersystems with high reliability and modularity requirements. The KRTM itself has been designed with the requirement for modifiability in mind, and therefore it is easy to obtain new versions of the kernel, adapted to a particular application.
Data organization in major-minor loop magnetic bubble memory is described, including an analysis of sequential and random accessing. A typical sorting application is described and analyzed, including information on op...
详细信息
Data organization in major-minor loop magnetic bubble memory is described, including an analysis of sequential and random accessing. A typical sorting application is described and analyzed, including information on optimal algorithms, buffering criteria, and run time. Deviations from this example are presented and analyzed, including highly parallel systems, highly independent systems, and a range of floating buffering schemes.
Data parallelism has appeared as a fruitful approach to the parallelisation of compute-intensive programs. Data parallelism has the advantage of mimicking the sequential (and deterministic) structure of programs as op...
详细信息
Data parallelism has appeared as a fruitful approach to the parallelisation of compute-intensive programs. Data parallelism has the advantage of mimicking the sequential (and deterministic) structure of programs as opposed to task parallelism, where the explicit interaction of processes has to be programmed. In data parallelism data structures, typically collection classes in the form of large arrays, are distributed on the processors of the target parallel machine. Trying to extract distribution aspects from conventional code often runs into problems with a lack of uniformity in the use of the data structures and in the expression of data dependency patterns within the code. Here we propose a framework with two conceptual classes, Machine and Collection. The Machine class abstracts hardware communication and distribution properties. This gives a programmer high-level access to the important parts of the low-level architecture. The Machine class may readily be used in the implementation of a Collection class, giving the programmer full control of the parallel distribution of data, as well as allowing normal sequential implementation of this class. Any program using such a collection class will be parallelisable, without requiring any modification, by choosing between sequential and parallel versions at link time. Experiments with a commercial application, built using the Sophus library which uses this approach to parallelisation, show good parallel speed-ups, without any adaptation of the application program being needed.
A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is ...
详细信息
A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n**2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.
Most object-oriented systems lack two useful facilities: the ability of objects to migrate to new environments and the ability of objects to acquire new operations dynamically. This paper proposes Knos, an object-orie...
详细信息
Most object-oriented systems lack two useful facilities: the ability of objects to migrate to new environments and the ability of objects to acquire new operations dynamically. This paper proposes Knos, an object-oriented environment that supports these actions. Knos' operations, data structures, and communication mechanisms are discussed. Knos objects “learn” by exporting and importing new or modified operations. The use of such objects as intellectual support tools is outlined. In particular, various applications involving cooperation, negotiation, and apprenticeship among objects are described.
The concepts of structured programming attempt to provide a rational basis for writing programs with useful and easily understood structures. As well, they promote a programming methodology called stepwise constructio...
详细信息
The concepts of structured programming attempt to provide a rational basis for writing programs with useful and easily understood structures. As well, they promote a programming methodology called stepwise construction, which is particularly valuable in the design of large and complex program. This paper describes the design and implementation of a language for structured programming - SPL.
暂无评论