Software complexity is acutely recognized as the major reason for rapidly increasing software development cost. To deal with this problem effectively, software complexity metrics have been perceived as a critical element of software development. With the increased use of concurrent and distributed computing in wide range of applications, a need exists for techniques which can be used to aid in development of correct and reliable distributed software. Controlling, or at least recognizing, complexity of such software is an important part of the development and maintenance process. But, despite numerous metrics to measure the complexity of sequential programs, software complexity metrics are almost nonexistent for concurrent programs.
In this dissertation, we propose a model and metrics which quantize the complexity of concurrent programs. As primary factors that complicate the processes of understanding and developing of concurrent programs, information content, the amount of intertasking activity, nondeterminism and accessibility are identified. The primary notion of program complexity germane to this dissertation is a notion of the quantified amount of information needed to resolve any uncertainty manifested through the program. Hence, the proposed metrics are based on the entropy function of communication theory which is well-justified measures of uncertainty.
An execution of a concurrent program can be interpreted as an experiment that selects, from all possible ways that a program allows, the single correct configuration for that execution. The information content is used to measure the uncertainty contained in this experiment. The metric for intertasking measures the amount of information caused through task coordination. And the metric for nondeterminism can be used to measure the uncertainty which may be occurred by nondeterministic features in a concurrent program. The information content, the amount of intertasking activity and the nondeterminism contained in a concurrent program are measured in terms of the information represented on the corresponding concurrency graph. These metrics provide interesting complexity measures upon which to base behavior of a concurrent program. Unfortunately the number of states in a concurrency graph can be very large, thereby limiting the programs that can be measured. To cope with this problem, we develop an additional metric. The metric for accessibility is used to measure the number of bits required to encode a given program. The time complexity of evaluating the metric of accessibility is on the order of the number of tasking related constructs in the corresponding task flow graph.
Using Ada as a model language, we show how to define the information theoretical complexity metrics and illustrate the implications with examples. To assess the significance of the proposed metics, we discuss the generalized behavior exhibited by the metrics against a list of software metric evaluation criteria. In addition, we also present experimental results for some standard examples from concurrent programs literature.
본 논문에서는 병행 프로그램에 내재된 복잡도를 정량화하기 위한 모델과 이에 따른 복잡도 척도들을 개발하였다. 제안된 복잡도 척도들은 병행 프로그램을 이해하고 개발하는 과정을 어렵게하는 주요한 요인들을 측정하기 위한 척도들이다. 본 논문에서는 복잡도를 프로그램에 내재된 불확실성을 해소하기 위하여 필요한 정량화된 정보량으로 해석하였다. 따라서 제안된 복잡도 척도들은 불확실성의 척도로 정립된 엔트로피 함수를 이용하여 정의되었다.
병행 프로그램에 대한 복잡도 척도에 앞서서, 병행 프로그램의 전체 복잡도를 순차적 복잡도와 병행적 복잡도의 두 부분의 결합으로 정의하여 이질적인 두 부분을 동일한 측정단위를 갖는 통합된 형태로 정의할 수 있는 기반 개념을 정의하였다. 본 논문에서 개발된 복잡도 척도들은 측정 대상에 따라서 두가지 형태로 나뉜다. 병행 프로그램의 행동 특성에 따른 복잡도를 정량화 하기위한 복잡도 척도들로는 병행 프로그램의 수행에 내재되어 있는 무질서의 정도를 측정하기 위한 정보량에 대한 척도, 프로그램이 이상 상태에 이를 정도를 나타내는 이상상태비, 태스크들간의 동기화에 따른 복잡도를 위한 동기화 정도 척도, 주어진 프로그램에 내재된 비결정성의 정도를 측정하는 척도들이 포함된다. 이들 척도들은 병행 프로그램의 행동 특성을 표현하는 병행그래프를 이용하여 정의되었기 때문에 계산량이 많다는 단점을 지닌다. 따라서 본 논문에서는 손쉽게 계산할 수 있는 또다른 복잡도 척도인 빈도량에 대한 척도를 제안하였다. 빈도량 척도는 병행 프로그램을 이해하는데 필요한 최소한의 결정횟수를 표현한 것이며, 태스크 흐름 그래프를 이용하여 정의 하였다. 본 논문에서 개발한 복잡도 척도들에 대한 타당성 평가를 위하여 이론적 평가와 실험을 수행하였다. 이론적 평가로는 척도가 만족해야 할 추상적인 특성을 정의하고 제안된 척도가 이를 만족하는 지를 평가하였다. 또한 병행 프로그램에 대한 연구 분야에서 대표적으로 언급되는 여러가지 문제들에 대한 실질적인 실험을 통하여 제안된 척도들이 유용성을 보였다.
