정보이론을 이용한 병행 프로그램의 복잡도 척도 = Complexity Metrics for Concurrent Programs Based on Information Theory

국문 초록 (Abstract)

순차적 프로그램의 복잡도를 측정하기 위한 많은 연구에도 불구하고 병행그램의 복잡도 척도에 관한 연구는 미미한 편이다. 본 논문에서는 병행 프로그램의 복잡도를 측정하기 위하여 정보이론에 근거를 둔 새로운 복잡도 척도를 제안한다. 제안된 복잡도 척도는 병행 프로그램을 복잡하게 만다는 요인으로 인식되는 정보량, 비결정성 및 동기화로부터 기인하는 복잡도를 측정한다. 제안된 복잡도 척도를 구하기 위하여 병행 프로그램의 표현 방법으로 병행 프로그램의 정적 분석에 이용되는 병행 그래프를 사용한다. 제안된 방법을 대표적인 병행 프로그램 언어인 Ada에 적용하여 그 유용성을 보여준다.

다국어 초록 (Multilingual Abstract)

Despite various researches for measuring the complexity of sequential programs, few attempts have been made to measure the complexity of concurrent programs. In this paper, we present new complexity metrics based on information theory which can measure the complexity of concurrent programs. Proposed metries measure primary factors influencing concurrent program's complexity such as information content, nondeterminism and intertasking. In order to compute the complexity, we use the concurrency graph previously developed for static analysis of concurrent programs. Using Ada as a model language, we show how to define proposed metrics and illustrate the implications with examples.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 2. 병행 그래프
• 3. 병행 프로그램의 정보량
• 4. 동기화 정도 척도
• 5. 비결정성 척도
• 6. 제안된 척도의 성질
• 7. 결론
• 참고문헌
• 저자소개