Since the interactions among processes of a parallel program are intrinsically nondeterministic, parallel programs often yield different results on repeated runs with the same input data. This non-reproducibility makes it extremely difficult to debug parallel programs. In addition, the interactions may be interfered with and even changed by extra codes inserted into the original program for debugging purpose. This phenomena, called probe effects, is another serious obstacle.
Guaranteeing reproducibility and minimizing probe effects are major issues in the parallel program debugging. This thesis suggests a new debugging method, named detect and reproduce method, for message-based parallel programs. This proposed method guarantees the reproducible behaviors of a target program. It is also devised to alleviate probe effects by reducing both the number of the probes to be inserted into a program and the amount of information gathered by those probes. Uniqueness of this method arises from the fact that it employs a static analysis technique to detect nondeterminacy. By detecting nondeterminacy before running the program, only a small number of probes are required to assure reproducibility. To analyze message-based programs statically, an MHB model is designed to catch the synchronization structures and a few algorithms have been developed to locate nondeterminacy based on the MHB model. Based on the analysis results, probes are inserted only into the places where nondeterminacy may occur.
메시지 전달에 기반을 둔 병렬 프로그램은 동시에 수행 가능한 다수의 프로세스와 그들간의 상호작용으로 구성된다. 이 때 프로세스들간의 병렬성 때문에 상호작용이 비결정적 특성을 지닌다. 즉, 프로그램을 동일한 입력에 대해서 반복 수행했을 경우에 서로 다른 상호작용이 발생할 수있고 따라서 서로 다른 결과가 산출될 수 있다. 비결정성을 내포한 병렬 프로그램을 디버깅할 때는 두가지 문제점이 발생한다. 첫째, 에러의 원인을 찾기가 어렵다. 반복 수행시에 동일한 결과가 보장되지 않으므로 한번 발생했던 에러에 대해서 다시 조사하기가 쉽지않다. 둘째, 디버깅을 위해서 삽입된 특수용도의 코드들이 프로세스 상호작용을 방해하고 변경시킨다. 결과적으로, 프로그램의 원래 동작을 관찰하기 어렵다.
따라서, 병렬 프로그램 디버깅을 위해서는 재수행성(reproducibility)을 보장하고 탐침효과(probe effects)를 최소화하는 기법이 필요하다. 본 논문에서는 탐침효과를 최소화한 재수행성 보장기법인 검출 후 재수행(Detect and Reproduce) 방법을 제안한다. 제안된 방법의 핵심은 비결정성 검출 시기를 앞당기는 데 있다. 기존의 방법들은 프로그램 수행중에 비결정성을 검출하고자 하기 때문에 많은 탐침효과를 유발한다. 반면에 이 방법은 수행전에 비결정성의 위치와 원인을 미리 검출하고 수행중에는 단지 비결정성의 결과만을 기록한다. 따라서, 수행중의 탐침효과를 크게 줄일 수 있고 재수행성도 보장할 수 있다. 이 방법은 정적분석 단계와 정적분석 정보를 바탕으로하는 재수행 단계로 나뉜다.
정적 분석 단계는 최소 선후 관계(MHB, Minimal Happened Before)에 기반을 두고 있다. MHB는 메시지 기반 병렬 프로그램의 동기화 구조를 모델링하기 위해서 본 논문에서 제안된 모델로서 메시지 전달에 사용되는 채널의 동기적 속성을 표현한다. 프로그램 내의 메시지 송신 문장과 수신 문장 사이에는 항상 만족되는 선후 관계가 존재하게 된다. 메시지 수신 문장은 송신 문장에서 메시지를 보내기 전에는 메시지를 받을 수 없다는 특성이 있고 반대로 메시지를 받을 수 있는 수신 문장이 없는 경우에 송신 문장에서는 메시지를 전달할 수가 없다. MHB는 이 두가지 선후 관계를 모델링한다. MHB의 중요한 특성은 MHB에 의해 모델링 된 선후관계가 프로그램 수행시에 항상 만족된다는 점이다. MHB에 의해 표현된 선후관계가 모든 시나리오에 대해서 만족되므로 이에 기반을 둔 분석 방법들은 발생 가능한 모든 비결정성을 찾아낼 수 있다. 즉, 분석방법들이 완전성(completeness)을 가진다. 또한 생성 가능한 모든 시나리오를 나열식으로 분석하는 다른 방법들과 달리 MHB는 모든 경우에 만족되는 선후관계만을 분석하므로 분석으로 인한 과부하가 매우 적다.
재수행 단계는 정적 분석 단계에서 검출된 결과를 바탕으로 어떤 정보를 수행중에 기록해야 추후에 재수행이 가능할 것인지를 판별한다. 또한 정보 수집을 위해서 프로그램의 어느 부분에 어떤 종류의 코드를 삽입해야 할 것인지를 결정하고 결정된 부분에 코드를 삽입한다. 프로그램 수행중에 에러가 발생하면 수집된 수행정보를 바탕으로 재수행을 보장해야 하는데 여기서는 비결정성을 지닌 문장들로부터 비결정성을 제거함으로써 재수행성을 보장한다. 예를 들어서 비결정성을 지닌 select 문장의 경우에 switch/case 문장으로 변환함으로써 비결정성을 제거한다.
본 논문에서는 탐침효과를 최소화한 새로운 디버깅 방법을 제안했다. 또한 이 방법이 재수행성을 보장함을 보였고 기존의 방법들에 비해서 탐침효과를 감소 시킬 수 있음을 보였다. 그리고 재수행을 위해서 수집되는 정보의 양도 크게 늘어나지 않음을 보였다. 디버깅시에 정적 분석 방법을 사용해서 프로그램 내의 비결정성을 검출하는 시점을 앞당김으로써 이상과 같은 효과를 얻을 수 있었으며 정적 분석을 위한 MHB 모델과 분석 방법을 제안했다. 이 방법의 효과는 정적 분석의 결과가 얼마나 정확한가에 영향을 받게 되는데 본 논문에서는 분석 방법의 완전성(completeness)은 입증했으나 정확성(compactness) 문제는 정적 분석의 근본적 한계와 관련된 문제이므로 입증하지 못했다. 이 부분에 대한 연구가 뒤따라야 할 것이며 MHB 모델의 정확성을 향상시키기 위한 연구가 필요하다.
