Parallel Machine에 있어서의 Functional, Declarative 언어의 Algorithm

김진수,Kim, Jin-Su 배재대학교 자연과학연구소 1992 自然科學論文集 Vol.5 No.2

사용자의 관점에서 볼때는 compiler가 parallelism을 발견할 수 있게 하는것이 매우 요구되지만, 아무리 잘 만들어진 compiler 라 할지라도 conditional, functional 또는 I/O statement 등 프로그램내에 존재하는 많은 parallelism을 인식 하기가 결코 쉬운 일이 아니다. 경우에 따라서는 compiler의 parallelism 결정이 곤란할경우 사용자에게 feedback 시키는 경우가 종종 있다. 이런 입장에서 프로그래머는 parallelism을 바로 전달하기 위해서 프로그램의 일부를 재구성 시킬 필요가 자주 발생한다. 그러한 관점에서 Functional, Declarative 언어의 잇점이 있다고 할 수 있고, 그러기 위해서는 paralled machine에 적합한 Algorithm 이 필요하다. 그러나, 이미 사용중인 Algorithm이 Parallel Machine에 부적절 하다는 것을 의미 하는것은 아니다. 본 연구에서는, Fortran을 이용하여 Parallel Algorithm을 구현 시키기위한 Declarative 언어에 있어서 Array 및 Matrix 를 다루기위한 Abstraction 방법을 제시 하고자 한다. Detection of parallelism by a compiler is very desirable from a user's point of view. However, even the most sophisticated techniques to detect parallelism trip on trivial impediments, such as conditionals, function calls, and input/output statements, fail to detect most of the parallelism present in a program. Some parallelizing compilers provide feedback to the user when they have difficulty in deciding about parallel execution. Under these circumstances, a programmer has to restructure the source code to aid the detection of parallelism. But, functional and declarative languages can be said to offer many advantages in this context. Functional programs are easier to reason about because their output is determinate, that is, independent of the order of evaluation. However, functional languages traditionally have lacked good facilities for manipulating arrays and matrices. In this paper, a declarative language called Id has been proposed as a solution to some of these problems.

Performance Comparison of Parallel Programming Frameworks in Digital Image Transformation

신우창 한국인터넷방송통신학회 2019 International Journal of Internet, Broadcasting an Vol.11 No.3

Previously, parallel computing was mainly used in areas requiring high computing performance, but nowadays, multicore CPUs and GPUs have become widespread, and parallel programming advantages can be obtained even in a PC environment. Various parallel programming frameworks using multicore CPUs such as OpenMP and PPL have been announced. Nvidia and AMD have developed parallel programming platforms and APIs for program developers to take advantage of multicore GPUs on their graphics cards. In this paper, we develop digital image transformation programs that runs on each of the major parallel programming frameworks, and measure the execution time. We analyze the characteristics of each framework through the execution time comparison. Also a constant K indicating the ratio of program execution time between different parallel computing environments is presented. Using this, it is possible to predict rough execution time without implementing a parallel program.

OpenMP Parallel Programming Using Dual-Core Embedded System

Kyung Min Lee,Tae Houn Song,Seung Hyun Yoon,Key Ho Kwon,Jae Wook Jeon 제어로봇시스템학회 2011 제어로봇시스템학회 국제학술대회 논문집 Vol.2011 No.10

Multi-cores have recently been applied to smartphones, as well as PCs; the performance of electronic devices is improving. However, there is no improvement in performance, if the existing sequential program is executed on multi-core processors. Parallel programming is necessary to use multi-core processors well. Already some companies are doing projects to parallel their own programs that are executed in the PC environment, for example, Adobe Systems Inc., Autodesk Inc., and Epic Games Inc. However, very few embedded field studies, focus on parallel programming. In this paper, we study a parallel programming model, OpenMP, and parallel programs that can be benchmarked to multi-core processors of embedded boards using OpenMP. We execute parallel programs on a dual-core embedded system. We analyze the performance of sequential programs and parallel programs by SERPOP analysis. Finally, we reduce the execution time of programs by a mean of 111%.

순수 함수형 언어로 작성된 쌍방시뮬레이션 알고리듬의 성능을 병렬화로 향상시키는 방법 연구

안기영(Ki Yung Ahn) 한국컴퓨터정보학회 2021 韓國컴퓨터情報學會論文誌 Vol.26 No.1

본 논문에서는 순수 함수형 언어로 작성된 쌍방시뮬레이션 알고리듬의 성능을 멀티코어 프로세서 컴퓨터에서 병렬화로 향상시키는 방법을 연구한다. 이 병렬화에 있어 핵심 아이디어는 순수함수형 프로그램의 참조 투명성을 십분 활용하면 병렬화가 전혀 고려되지 않고 작성된 초기 구현으로부터 최소한의 수정만으로 성능 개선 효과를 기대할 수 있다는 것이다. 초기 구현과 병렬화 구현 둘 다 순수 함수형 언어인 하스켈로 작성되었다. 초기 구현을 병렬화할 때 변화는 아주 적어서 병렬화된 구현에서도 초기 구현의 프로그램 구조가 거의 그대로 유지되었다. 벤치마크를 통해 제시된 간단한 병렬화만으로도 초기 구현과 비교해 두 배 이상의 성능 개선을 확인했다. 또한, 병렬화와는 별개의 최적화 기법인 메모이제이션이 적용된 버전의 쌍방시뮬레이션 구현에도 같은 방식의 병렬화를 적용함으로써 마찬가지로 성능을 개선할 수 있음을 확인하였다. In this paper, we demonstrate a performance boost by parallelizing a purely functional bisimulation algorithm on a multicore processor machine. The key idea of this parallelization is exploiting the referential transparency of purely functional programs to minimize refactoring of the original implementation without any parallel constructs. Both original and parallel implementations are written in Haskell, a purely functional programming language. The change from the original program to the parallel program is minuscule, maintaining almost original structure of the program. Through benchmark, we show that the proposed parallelization doubles the performance of the bisimulation test compared to the original non-parallel implementation. We also shaw that similar performance boost is also possible for a memoized version of the bisimulation implementation.

GC-Tune을 이용한 Haskell 병렬 프로그램의 성능 조정

김화목(Hwamok Kim),안형준(Hyungjun An),변석우(Sugwoo Byun),우균(Gyun Woo) 한국정보과학회 2017 정보과학회 컴퓨팅의 실제 논문지 Vol.23 No.8

매니코어 기술에 힘입어 컴퓨터 하드웨어의 성능이 향상되고 있지만 그에 비례한 소프트웨어 성능 증가는 다소 미미한 실정이다. 함수형 언어는 병렬 프로그램의 성능을 향상시키는 대안 중 하나이다. 이러한 언어는 부수효과가 없는 순수한 수식을 통해 내재된 병렬성을 지원하기 때문이다. 함수형 언어인 Haskell은 모나드를 기반으로 하는 다양하고 쉬운 병렬 구조를 제공하기 때문에 병렬 프로그래밍에서 널리 사용된다. 하지만 Haskell로 작성된 병렬 프로그램의 성능 확장성은 코어 수가 증가함에 따라 변동이 큰 경향이 있다. 이는 프로그램 실행에 있어 가비지 컬렉션이 공간과 시간에 모두 영향을 미치는데 Haskell은 이러한 가비지 컬렉션을 사용하는 가상머신 위에서 실행되기 때문이라고 추정된다. 따라서 본 논문에서는 GC-Tune이라는 메모리 튜닝 도구를 사용하여 이 추정이 맞는지 검증하고 Haskell 병렬 프로그램의 성능확장성을 높이는 방법을 모색한다. 병렬 Haskell 표절 검사 프로그램을 대상으로 실험한 결과 성능 확장성이 향상되었다. 특히 메모리 튜닝을 하지 않은 프로그램에 비해 속도 향상의 변동 범위가 39% 감소하였다. Although the performance of computer hardware is increasing due to the development of manycore technologies, software lacking a proportional increase in throughput. Functional languages can be a viable alternative to improve the performance of parallel programs since such languages have an inherent parallelism in evaluating pure expressions without side-effects. Specifically, Haskell is notably popular for parallel programming because it provides easy-to-use parallel constructs based on monads. However, the scalability of parallel programs in Haskell tends to fluctuate as the number of cores increases, and the garbage collector is suspected to be the source of this fluctuations because it affects both the space and the time needed to execute the programs. This paper uses the tuning tool, GC-Tune, to improve the scalability of the performance. Our experiment was conducted with a parallel plagiarism detection program, and the scalability improved. Specifically, the fluctuation range of the speedup was narrowed down by 39% compared to the original execution of the program without any tuning.

불변 및 가변 루프구조의 병렬성 제고를 위한 프로그램 재구조화

송월봉 한국지식정보기술학회 2012 한국지식정보기술학회 논문지 Vol.7 No.2

The general methods for the extracting parallelism in order to parallel processing effectively are unimodular transformation which restructure a nested loop and non-unimodular transformation for using effectively hierarchy memory device. This paper compare and analyze this two algorithm. And also propose mixed method in order to raising the parallelism. From now on, this result will be applied to the bench mark program like a perfect benchmark program and introduced in the real problem and I plan to propose a general parallel compiler.

Online Integrated Development Environment for MapReduce Programming

Zhiqiang Ma,Shuangtao Yang,Zhida Shi,Rui Yan 보안공학연구지원센터 2016 International Journal of u- and e- Service, Scienc Vol.9 No.6

Though MapReduce programming model simplifies the development of parallel program, ordinary users have difficulties in setting up the development environment for MapReduce. The online integrated development environment for MapReduce programming can solve this problem, thus users need not build the environment themselves, only need to focus on the logical design of the parallel program. During the software construction, the problem of independent space setting and naming conflict of the file in the multi-user environment, and the problem of online compiling, execution and instant feedback message to client are solved. The software has been deployed and tested in Hadoop cluster, and can meet users’ basic requirements for the development of MapReduce.

Parallel task scheduling under multi-Clouds

( Yongsheng Hao ),( Mandan Xia ),( Na Wen ),( Rongtao Hou ),( Hua Deng ),( Lina Wang ),( Qin Wang ) 한국인터넷정보학회 2017 KSII Transactions on Internet and Information Syst Vol.11 No.1

In the Cloud, for the scheduling of parallel jobs, there are many tasks in a job and those tasks are executed concurrently on different VMs (Visual machines), where each task of the job will be executed synchronously. The goal of scheduling is to reduce the execution time and to keep the fairness between jobs to prevent some jobs from waiting more time than others. We propose a Cloud model which has multiple Clouds, and under this model, jobs are in different lists according to the waiting time of the jobs and every job has different parallelism. At the same time, a new method-ZOMT (the scheduling parallel tasks based on ZERO-ONE scheduling with multiple targets) is proposed to solve the problem of scheduling parallel jobs in the Cloud. Simulations of ZOMT, AFCFS (Adapted First Come First Served), LJFS (Largest Job First Served) and Fair are executed to test the performance of those methods. Metrics about the waiting time, and response time are used to test the performance of ZOMT. The simulation results have shown that ZOMT not only reduces waiting time and response time, but also provides fairness to jobs.

A Survey of Loop Parallelization: Models, Approaches, and Recent Developments

Hong Yao,Huifang Deng,Caifeng Zou 보안공학연구지원센터 2016 International Journal of Grid and Distributed Comp Vol.9 No.11

In cloud computing era, automatic parallelization is still significant for virtualization platform. However, after several decades of development, the overall effect is still to be improved. Summary of the mainstream technology developments will be beneficial to reveal the future direction and trend. This paper reviews the technology of loop parallelization, which is the key issue in automatic parallelization. After introducing the basic models and approaches, we focus on the recent developments, on which we obtain the trend of this field and the conclusions about future.

성김도 정책에 의한 병렬 프로그램의 성능 평가

송인근 우송대학교 부설 산업연구원 1999 산업연구 Vol.1 No.1

The performance of parallel programs has suffered from the latencies caused by memory access and synchronization. To explore the effect of these latencies, we execute parallel applications varying the scheduling policies and grain sizes. The variations of the memory access patterms generated by the granularity and scheduling policies may affect the cache behavior and synchronization operatioin of the parallel applications. In this paper, the interactions between grain sizes and scheduling policies are examined through execution-driven simulations. The simulatioin results show that the grain size and scheduling policy selected by the programmers have significant impacts on the cache behavior and synchronization latency in most parallel programs. On the basis of the simulation studies, we suggest the best grain size and scheduling policy for each simulated parallel program, and analyze the causes inducing those results.