본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보과학회논문지. Journal of KIISE. 시스템 및 이론 v.29 no.12, 2002년, pp.655 - 664  
본 등재정보는 저널의 등재정보를 참고하여 보여주는 베타서비스로 정확한 논문의 등재여부는 등재기관에 확인하시기 바랍니다.

다중스레드 데이타 병렬 프로그램의 표현 : PCFG(Parallel Control Flow Graph)
A Representation for Multithreaded Data-parallel Programs : PCFG(Parallel Control Flow Graph)

김정환   (건국대학교 컴퓨터·응용과학부UU0000050  );
  • 초록

    데이타 병렬 모델은 대규모 병렬성을 용이하게 얻을 수 있는 장점이 있지만, 데이타 분산으로 인한 통신 지연시간은 상당한 부담이 된다. 본 논문에서는 데이타 병렬 프로그램에 내재되어 있는 태스크 병렬성을 추출하여 이러한 통신 지연시간을 감추는데 이용할 수 있음을 보인다. 기존의 태스크 병렬성 추출은 데이타 병렬성을 고려하지 않았지만, 여기서는 데이타 병렬성을 그대로 유지하면서 태스크 병렬성을 활용하는 방법에 대해 설명한다. 데이타 병렬 루프를 포함할 수 있는 다수의 태스크 스레드들로 구성된 다중스레드 프로그램을 표현하기 위해 본 논문에서는 PCFG(Parallel Control Flow Graph)라는 표현 형태를 제안한다. PCFG는 단일 스레드인 원시 데이타 병렬 프로그램으로부터 HDG(Hierarchical Dependence Graph)를 통해 생성될 수 있으며, 또한 PCFG로부터 다중스레드 코드를 쉽게 생성할 수 있다.


    In many data-parallel applications massive parallelism can be easily extracted through data distribution. But it often causes very long communication latency. This paper shows that task parallelism, which is extracted from data-parallel programs, can be exploited to hide such communication latency Unlike the most previous researches over exploitation of task parallelism which has not been considered together with data parallelism, this paper describes exploitation of task parallelism in the context of data parallelism. PCFG(Parallel Control Flow Graph) is proposed to represent a multithreaded program consisting of a few task threads each of which can include a few data-parallel loops. It is also described how a PCFG is constructed from a source data-parallel program through HDG(Hierarchical Dependence Graph) and how the multithreaded program can be constructed from the PCFG.


  • 주제어

    데이타 병렬성 .   태스크 병렬성 .   다중스레드 .   제어 흐름 그래프 .   병렬 제어 흐름 그래프 .   제어 종속성 .   데이타 종속성 .   통신 지연시간.  

  • 참고문헌 (16)

    1. R. v. Hanxleden and K. Kennedy, 'A Code Placement Framework and its Application to Communication Generation,' CRPC-TR93337-S, Center for Research on Parallel Computation, Oct. 1993 
    2. Message Passing Interface Forum, MPI: A Message Passing Interface Standard, June 12, 1995 
    3. D. Callahan and K. Kennedy, 'Analysis of Inter-procedural Side Effects in a Parallel Programming Environment,' Journal of Supercomputing, October, 1988 
    4. M. Kandemir, P. Banerjee, A. Choudhary, J. Ramanujam and N. Shenoy, 'A Global Communication Optimization Technique Based on Data-Flow Analysis and Linear Algebra,' ACM Transaction on Programming Languages and Systems, Vol. 21, No. 6, November 1999, pp. 1251-1297 
    5. C. Koelbel and P. Mehrotra, 'Programming Data Parallel Algorithms on Distributed Memory Machines using Kali,' Proceedings of the 1991 ACM International Conference on Supercomputing, June 1991 
    6. J. Wu, J. Saltz, H. Berryman and S. Hiranandani, 'Distributed Memory Compiler Design for Sparse Problems,' ICASE Report 91-13, Hampton, VA, January 1991 
    7. Constantine D. Polychronopoulos, 'The Hierarchical Task Graph and its Use in Auto-Scheduling,' Proceedings of the 5th International Conference on Supercomputing, June 1991 
    8. Milind Girkar, Constantine D. Polychronopoulos, 'The HTG: An Intermediate Representation for Program Based on Control and Data Dependences,' Tech. Rep. No. 1046, Center for Supercomputing Res. and Dev. - University of Illinois, May 1991 
    9. Robert A. Ballance, Arthur B. Maccabe and Karl J. Ottenstein, 'The Program Dependence Web: A Representation Supporting Control-, Data-, and Demand-Driven Intrepretation of Imperative Languages,' ACM SIGPLAN Notices, Proceedings of the Conference on Programming Language Design and Implementation, Vol. 25, Issue 6, June 1990, pp. 257-271 
    10. Keshav Pingali, Micah Beck, Richard Johnson, Mayan Moudgill and Paul Stodghill, 'Dependence Flow Graphs: An Algebraic Approach to Program Dependencies,' Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 1991 
    11. Richard Johnson and Keshav Pingali, 'Dependence-Based Program Analysis,' ACM Programming Language Design and Implementation, ACM SIGPLAN Notices, Proceedings of the Conference on Programming Language Design and Implementation, Vol. 28, Issue 6, JUne 1993, pp. 78-89 
    12. J. Ferrante, K. J. Ottenstein and J. D. Warren, 'The Program Dependency Graph and Its Uses in Optimization,' ACM Trans. on Programming Languages and Systems, Vol. 9, No. 3, June 1987, pp. 319-349 
    13. A. V. Aho, R. Sethi and J. D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading, MA, 1986 
    14. S. Hiranandani, K. Kennedy and C. Tseng, 'Evaluation of Compiler Optimizations for Fortran D on MIMD Distributed-Memory Machines,' Proc. of the 1992 ACM Intl Conference on Supercomputing, Washington DC, July 1992 
    15. Milind Girkar, Constantine D. Polychronopoulos, 'Extracting Task-Level Parallelism,' ACM Transaction on Programming Languages and Systems, Vol. 17, No. 4, July 1995, pp. 600-534 
    16. David F. Bacon, Susan L. Graham and Oliver J. Sharp, 'Compiler Transformation for High-Performance Computing,' ACM Computing Surveys, vol. 26, No. 4, December 1994, pp. 345-420 

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기