Parallel processing and parallel processing applications in image parameter - Chu Duc Toan

Chu Đức Toàn Tạp chí KHOA HỌC & CÔNG NGHỆ 93(05): 91 - 95 91 PARALLEL PROCESSING AND PARALLEL PROCESSING APPLICATIONS IN IMAGE PARAMETER Chu Duc Toan* Electric Power University ABSTRACT The science growth brings many problems with large volume of calculation, however, during a certain time. The examples are 3D image processing problems, oil exploration, forecasting, multiple-target follow-up system requiring fast computation speed, etc (sequential processing such as von Neumann does not meet requirements). To solve these problems, it is researched to speed up by two methods or a combination of two methods that are (1) technology improvement to increase computer-processing speed, requiring more time, more expenses but brings speed limited and (2) division of the problems into smaller tasks to run parallel on multiple processors (functional decomposition problem). The most important principle of parallel processing is simultaneity, or processing multiple tasks simultaneously. The paper generally studies about parallel processing system and application of parallel processing problem in image parameters for very good results and faster program Keywords: parallel processing system; calculation; process multiple tasks simultaneously; parallel processing image parameters, and increase processing speed. INTRODUCTION* Sequential computing with a processor carries out only a computation in one time. However, parallel processing can perform multiple operations simultaneously. So it involves many parameters, both hardware and software. Figure 1 shows a comparison between parallel programming and conventional programming. Developing control mechanisms of parallel processing requires following components: A-algorithm for parallel processing (Algorithm); L - Language, O-Object Code; M - Machine code MULTI-CPUPARALLEL PROCESSING SYSTEM Multi-CPU system can be characterized by two attributes: an independent processing system including multiple CPUs and which CPUs can contact and cooperate at various degrees in performing assigned tasks. Communication between CPUs performs by notifying each other or sharing common memory. * Tel: 0982 917093, Email: toancd@gmail.com Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chu Đức Toàn Tạp chí KHOA HỌC & CÔNG NGHỆ 93(05): 91 - 95 92 So many actions will occur simultaneously in the system and thus block controlling operation system is needed to provide ability of coordinating CPUs and their programs in data processing, settings and level, authority to handle them (Denel Hep system). Control block must be able to analyze each command cluster to form child processes with parallel properties, then optimally distribute to component CPU and provide the coordination method of these CPUs at all stages such as data arrangement, establishment, and data access level/ right control. We will construct parallel processing system with p CPU forming a p-dimensional linear vector space. During operation, each CPU may have to access many times to central memory to update data, thus increasing the latency of the system. To reduce this latency we organize Cache structure for each CPU. Thus, CPU has to access central memory in final stage only, which significantly reduces the queuing time in input /output between CPUs and central memory. Functional graph of this process is like Figure 2. Programming for multi-CPU parallel processing system The basic standard for central CPU to analyze and divide main functions into child functions is Beinstein. This means that if meeting parallel standard, a system can start a new process when old processes are ongoing. At this time, central CPU will use FORK and JOIN statements to describe operations. FORK is used to generate a new process: FORK A will start another process starting from address A and continue performing current process; FORK A, J perform as FORK A in addition to increasing counter value at address J; FORK A, J, N also perform like FORK A together with setting up counter at J to N value. Despite any form of FORK, JOIN statement has only one form which is JOIN J. When performing this statement, JOIN J will reduce one unit of J counter content. If the result is 0, then a process in J +1 will be initiated. In other words, processors implementing prior processes will be either completely free or prepared to implement new processes (Figure 3). Dikstra parallel programming languages with equivalent structure to FORK and JOIN statements are PARBegin and PAREnd (or COBegin and COEnd). Assuming that processes S1,S2,..,Sn can operate parallel as Beinstein standard, following command structures will start parallel these processes. Begin So; PARBegin S1;S2;...;Sn;PAREnd Sn+1 End The program must be written for easy interpreting, easy checking links to organize parallel processes and combinatorial variables for these processes. PARBegin declares that current program is divided into subcomponents which can operate simultaneously. This allows to use local variables and to share global variables without system conflicts. In Figure 4, PARBegin and PAREnd operate only after So already operated. Sn +1 is initiated only when the set of S1, S2, ..., Sn has ended. In this structure, one thing to note is that if a variable Vi is edited by manipulation Si, this variable cannot be referenced by manipulation Sj (for j i). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chu Đức Toàn Tạp chí KHOA HỌC & CÔNG NGHỆ 93(05): 91 - 95 93 APPLICATION PROBLEM: Parallel processing image parameters To illustrate the ability of above processing system, we consider the problem of processing Historgram parameter for black and white photos. Each image is represented by a set of pixels. After being processed, the parameters will be extended to other parameters and give color image in all forms. Figure 5. Processing p parallel processes Each pixel has a value from 0 to (b-1) correspondent to a value of gray scale of black and white photos. If one byte is used to store this value, each pixel will be valued from 0 to 255. Historgram is an important parameter form because it indicates the occurrence frequency of each value in image gray scale. Thus, quantity b must be updated and stored. If Histog [O:b-1] is used to represent array containing accumulated counts of gray-scale values 0,1, ..., b-1, a rectangular image will be represented by two- dimensional array of pixels [0: m-1, 0: n-1] with m is row and n is column. If pixel [i, j] represents gray-scale value at coordinates (i, j), it is easy to build a program for single-processor system controlling the updating of values: The update time will depend on the result of m * n. If m and n are very large, Histogram calculation takes a lot of time. Moreover, if information flow containing image data transmitted at high-speed to the processing system, sometimes the system cannot keep up processing and calculating. Now if the processing system has p CPU in parallel operation mode as the structures shown in Figure 2 and Figure 4, image line can be divided into p segment ensuring m / p = s line. Each CPU is in charge of calculating an array of s rows and n columns. So, we create p independent process launched in parallel. But it is noted that manipulation processes forming Histogzam has to share histog [0: b-1] array to update content for frequency counters. Decay rate is calculated as p (Figure 4 and Figure 5). Using PARFOR structure, we have program: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chu Đức Toàn Tạp chí KHOA HỌC & CÔNG NGHỆ 93(05): 91 - 95 94 Update time will depend on s * n result. It is clear that the speed is greatly increased. However in this case, speed cannot reach p times because processes has to share histog [0: b-1] counter outside central memory so they need queuing when accessing memory. If system architecture with Cache is used, the performance will be higher because memory access occurs only in final phase. At this time, the program can be replaced by a new structure: Var histog[0:b-1] : integer ; Initial histog[0:b-1] = 0 ; Var Ihistog[1: ;0:b-1] : integer; { local variable } Initial Ihistog[1:p,0:b-1] = 0 ; PARFor i < --- 1 until p do Begin Var pixel [(i-1)*s:S*i-1,0:n-1] : pixel; Var Ihistog[i,0:b -1] : integer; For k <--- (i-1)*s until S*i -1 do For j <--- 0 until n-1 do Ihistog[i,pixel [k,j]] --- Ihistog [i,pixel [k,j]]+1; End; For j <--- 0 until b-1 do { Total component histog } For i <--- 1 until p do Histog[i] <--- Histog[i] + Ihistog [i,j]; CONCLUSION Parallel processing allows to perform program faster and to utilize resources in processing system better. A process usually involves several steps of calculations and process. Using functional decomposition method is the main method to divide a task into child processes to conduct parallel operations. Histogzam image processing algorithm is an illustration for operation speed increase, especially when image data is multi- channel one transmitted from satellite. REFERENCES [1]. Do Xuan Tien et al. Report on the findings of scientific research "Design, manufacture the dump block of Uran-E missile test results on device automatically checking AKPA parameter made by Russian Federation", Hanoi 2008. [2]. Nguyen Minh Ngoc, Hoang Thi Phuong, Chu Duc Toan; about a piperline structure synthesizing method. Journal of Science and Engineering - Military Technical Academy, No. 123, II-2008 page 14-22 [3]. Deshanand P. Singh, Stephen D. Brown, The case for registered routing switches in field programmable gate arrays, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, pp. 161-169, February 2001, Monterey, California, United States. [4]. Kai Hwang Perdue University, Faye A. Biggs Rice University. Computer Architecture and Parallel and Processing. McGraw-Hill Book Company. 1999. [5]. Ashenhurst R.L.,The Decomposition of Switching Functions, Ann. Computation Lab., Harvard University, vol. 29, pp.74-116, 1959. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chu Đức Toàn Tạp chí KHOA HỌC & CÔNG NGHỆ 93(05): 91 - 95 95 TÓM TẮT XỬ LÝ SONG SONG VÀ ỨNG DỤNG XỬ LÝ SONG SONG CÁC THAM SỐ ẢNH Chu Đức Toàn* Đại học Điện lực Khoa học ngày càng phát triển, đạt ra nhiều bài toán có khối lượng tính toán rất lớn. Nhưng lại có yêu cầu trong một thời gian nhất định. Ví dụ như bài toán xử lý ảnh 3D, thăm dò dầu khí, dự báo, các hệ thống bám sát đa mục tiêu đòi hỏi tốc độ tính toán rất nhanh..(các xử lý tuần tự như von neumann không đáp ứng được yêu cầu). Để giải quyết bài toán người ta nghiên cứu tăng tốc độ bằng hai phương pháp hoặc kết hợp hai phương pháp là: Cải tiến công nghệ tăng tốc độ xử lý của máy tính. Đòi hỏi nhiều thời gian, tốn kém nhưng tốc độ vẫn chỉ giới hạn; Chia bài toán ra thành những công việc nhỏ để chạy song song trên nhiều bộ xử lý (bài toán phân rã chức năng). Nguyên tắc quan trọng nhất của xử lý song song là tính đồng thời hay xử lý nhiều tác vụ cùng một lúc. Bài báo nghiên cứu tổng quan về hệ xử lý song song và ứng dụng bài toán xử lý song song các tham số ảnh, cho kết quả rất tốt, chương trình nhanh hơn. Từ khóa: hệ xử lý song song; tính toán; xử lý nhiều tác vụ cùng lúc; xử lý song song các tham số ảnh; tăng tốc độ xử lý. Ngày nhận bài:24/2/2012, ngày phản biện: 14/3/2012, ngày duyệt đăng: * Tel: 0982 917093, Email: toancd@gmail.com Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên