Beyond striping: the bridge multiprocessor file system

ABSTRACT

High-performance parallel computers require high-performance file systems. Exotic I/O hardware will be of little use if file system software runs on a single processor of a many-processor machine. We believe that cost-effective I/O for large multiprocessors can best be obtained by spreading both data and file system computation over a large number of processors and disks. To assess the effectiveness of this approach, we have implemented a prototype system called Bridge, and have studied its performance on several data intensive applications, among them external sorting. A detailed analysis of our sorting algorithm indicates that Bridge can profitably be used on configurations in excess of one hundred processors with disks. Empirical results on a 32-processor implementation agree with the analysis, providing us with a high degree of confidence in this prediction. Based on our experience, we argue that file systems such as Bridge will satisfy the I/O needs of a wide range of parallel architectures and applications.

REFERENCES

• 1: [1] Butterfly¿ parallel processor overview. Technical Report 6149, Version 2, BBN Laboratories, June 1986.
• 2: Micah Beck , Dina Bitton , W. Kevin Wilkinson, Sorting Large Files on a Backend Multiprocessor, IEEE Transactions on Computers, v.37 n.7, p.769-778, July 1988 [doi>10.1109/12.2222]
• 3: Dina Bitton , David J. DeWitt , David K. Hsaio , Jaishankar Menon, A taxonomy of parallel sorting, ACM Computing Surveys (CSUR), v.16 n.3, p.287-318, Sept. 1984 [doi>10.1145/2514.2516]
• 4: [4] Peter Dibble, Michael Scott, and Carla Ellis. Bridge: A high-performance file system for parallel processors. In Proceedings of the Eighth International Conference on Distributed Computing Systems, pages 154-161, June 1988.
• 5: [5] Peter C. Dibble and Michael L. Scott. External sorting on a parallel interleaved file system. In 1989- 90 Computer Science and Computer Engineering Research Review. Department of Computer Science, University of Rochester, 1989.
• 6: G. A. Gibson , L. Hellerstein , R. M. Karp , D. A. Patterson, Failure correction techniques for large disk arrays, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.123-132, April 03-06, 1989, Boston, Massachusetts, United States
• 7: [7] R. F. Gurwitz, M. A. Dean, and R. E. Schantz. Programming support in the Cronus distributed operating system. In Proceedings of the Sixth International Conference on Distributed Computing Systems, pages 486-493, May 1986.
• 8: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 9: Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986
• 10: [10] Connection machine model CM-2 technical summary. Technical Report HA87-4, Thinking Machines Inc., April 1987.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories
      D.4.3 File Systems Management
          Subjects: Distributed file systems
      D.4.4 Communications Management
          Subjects: Input/output

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

General Terms:
Algorithms, Design, Performance, Verification