Efficient algorithms for memory and processor allocation in parallel processing systems

摘要

In this dissertation,optimal memory and processor allocation algorithms for parallel database processing are presented. Optimal memory allocation is one of the most important factors for preforming effective database query processing. In this dissertation, we discuss the memory resource allocation problem for the parallel database processing in the shared memory and distributed environments. We first introduce a stream-oriented parallel database processing scheme. This scheme has been designed for supporting advanced database applications in general purpose parallel processing environments. Then, we present formulas to describe the memory allocation problem for the stream-oriented parallel processing. After that, we prove two theorems for the optimal memory allocation problem. Finally, we present two new memory allocation algorithms for the stream-oriented parallel processing. By our algorithms, the optimal memory allocation is obtained for various databese queries in shared memory parallel processig environments and distributed processing environments. Another important factor for efficient parallel database processing is to allocate processors optimaly. In general, the optimal processor allocation of the parallel processing is NP-complete for distributed memory multiprocessor systems in which their communication network architectures are fixed. In order to reduce the complexity of the optimal processor allocatin, a reconfigurable multiprocessor system architecture PCVT is proposed. In the PCVT multiprocessor system, each processing element consists of a processor and a private memory. The processing elements are connected by a reconfigurable communication network. The significant characteristic of the PCVT system is that a physical communication path can be established dynamically between any two processing elements by the topology reconfiguration of the communication network. The architecture of the PCVT system, the topology reconfigration method of the communication network and a topology structure generation algorithm are presented in this dissertation. Finally, a processor allocation algorithm is presented.