http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : 최광무(Do-Hyung Kim) (검색결과 2 건)
- 무료
- 기관 내 무료
- 유료
-
논리 프로그램의 병렬 수행 모형에서 완결성과 효율성의 분석
김도형(Do-Hyung Kim),이수현(Su-Hyun Lee),최광무(Kwang-Moo Choe) 한국정보과학회 1996 정보과학회논문지(B) Vol.23 No.12
논리 프로그램(logic program)의 효율적인 병렬 수행을 위한 후방 수행(backward execution) 알고리즘들이 많이 제안되었다. 그 중 Conery와 Ng-Leung에 의해 제안된 방법들은 마크 집합(mark set)이라고 부르는 자료 구조를 사용하여 AND-병렬 수행 시 발생한 실패 경력(failure history)을 저장하고, 그것에 근거하여 백트랙 리터럴 선택과 재초기화(resetting) 수행한다. 두 알고리즘은 근본적으로 동일한 생각에 바탕을 두고 설계되었고 그 직관적 설득력 때문에 옳은 것으로 간주되어 왔다. 이 논문에서는 이들 알고리즘을 세밀히 분석하여 그것들이 수행하는 백트랙 리터럴 선택과 재초기화가 모두 틀림을 보인다. 그러한 오류가 어디에서 연유하였는지를 논의하고 또한 마크 집합 같은 자료 구조의 장점과 그 잠재적 가능성을 지적한 뒤, 마크 집합과 유사한 자료 구조를 사용하는 새로운 후방 수행 알고리즘을 제안하고 그 옳음을 증명한다. Conery and Ng-Leung have recently proposed two backward execution algorithms for efficient AND-parallel execution of logic programs, respectively. They adopt the same kind of data structure called mark (or marks) set to store information about failure history during AND-parallel evaluation of clauses. This mark-set data structure is used to select the backtrack literal for failure and to determine the literals to be reset. Both of the two algorithms essentially have the same rationale with minor differences and have been considered correct, largely due to their intuitive persuasiveness. We, however, closely re-examine those algorithms and find out that they are incorrect for both backtrack literal selection and resetting. Their incorrectness comes from oversimplifications about general failure situations. In this paper, our analyses focused on both the mark-set-based backtrack literal selection and resetting are presented. We also propose a backtrack literal selection and resetting method based on mark-set-like data structures after discussing merits and potential of the data structures, and prove the correctness of the method.
-
논리 프로그램의 병렬 수행에서 재초기화 알고리즘의 정확성 증명을 위한 참조 집합 : 직관적 접근
김도형,최광무(Do-Hyung Kim),Kwang-Moo Choe 한국정보과학회 1996 정보과학회논문지(B) Vol.23 No.3
논리 프로그램(logic program)의 병렬 수행 시, 중요한 작업 중의 하나인 재초기화(resetting)를 수행하기 위한 알고리즘들의 정확성(correctness) 증명을 위한 기준을 제시한다. 많은 연구자들이 논리 프로그램의 병렬 수행을 위한 수행 모형을 제안한 바 있고, 그것과 관련하여 재초기화를 효율적으로 처리하기 위한 알고리즘들을 제시하였다. 그러나 그 알고리즘들이 올바르게 작동하는 지에 대해서는 분명한 언급이 없는 경우가 많았다. 본 논문에서는 정확성에 대한 판단을 내릴 수 있는 기준을 도출한다. 이 도출 과정은 직관적으로 보아 명백한 사실에 대한 관찰로부터 유도되는 식으로 이루어진다. 도출된 정확성 판단 기준에 근거하여 기존의 재초기화 방법들을 점검하고, 보다 효율적이라고 판단되는 재초기화 방법도 서술한다. A criterion for the correctness proof of resetting algorithms in parallel execution of logic programs is suggested in the paper. Many researchers have proposed various execution models to exploit parallelism in logic programs, thus various algorithms to handle resetting efficiently. It is, however, hardly mentioned whether those algorithms are "really" correct in every case. In this paper, we devise a yardstick which may serve for probing the correctness of resetting algorithms. This criterion is derived from observations that are intuitively clear. According to the derived criteria, we analytically review existing schemes for resetting, and describe another new resetting method which seems to be more efficient than others.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
