Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Kiến trúc MISD bao gồm nhiều bộ xử lý. Mỗi bộ vi xử lý thực hiện các thiết lập của riêng độc đáo của nó hướng dẫn (Hình 16.3). Tuy nhiên, tất cả các bộ xử lý chia sẻ một dòng dữ liệu chung duy nhất. Bộ vi xử lý khác nhau thực hiện hướng dẫn khác nhau đồng thời cùng một luồng dữ liệu. Không có ví dụ thực tế của một MISD đã được xác định cho đến nay, và kiến trúc này vẫn còn hoàn toàn lý thuyết | Parallel Sorting Algorithms for MIMD with Shared Memory 237 Pivot 1 Pivot 2 Pivot 3 xk xk Illi Pivot p-I Pivot p sF sF Illi Yl Y2 Y3 Yp Figure 17.2. Schematic diagram of the calculation of pivots. where Max is the Maximum value of keys Min is the Minimum value of keys and n is the number of processors in the system. A schematic diagram is presented in Fig. 17.2. Yi is the sub-file after phase 1. This formula can still be used for non-uniform distribution. However preprocessing is required to map the non-uniform distribution to uniform distribution. Before the sorting starts a cumulative distribution table should be built using the method specified in many standard statistics textbooks. The pivot used in this algorithm can be found by mapping to the cumulative distribution table. A schematic diagram for the mapping is presented in Fig. 17.3. In this figure we split the file equally over five processors. We maintain the load balance by allocating approximately equal numbers of keys to each processor. 17.4.3.2 Performance Additional storage of n keys is required only at phase 2 and thus the storage requirement is 2n . However the storage of the old array will be released after this phase. This algorithm has the following properties Better than parallel Quicksort algorithm on average. Easily applied to difference kinds of distribution pattern of the input data file. Cumulative distribution Key value of non- __ uniform distribution Figure 17.3. Mapping of non-uniform distribution. 238 17. Distributed and Parallel Algorithms Eliminates the low amount of parallelism at the beginning of parallel Quicksort algorithm. Has a good speedup. 17.5 Parallel Sorting Algorithms for MIMD with Distributed Memory Since the final sorted file is distributed over different local memory computers a new definition of sorting is required. The sorting model is briefly described in the next section. 17.5.1 Definition of Distributed Sorting A large file is physically distributed in the
