DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Choe, Kwang-Moo | - |
dc.contributor.advisor | 최광무 | - |
dc.contributor.author | Lee, Su-Hyun | - |
dc.contributor.author | 이수현 | - |
dc.date.accessioned | 2011-12-13T05:23:08Z | - |
dc.date.available | 2011-12-13T05:23:08Z | - |
dc.date.issued | 1994 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=69678&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/33019 | - |
dc.description | 학위논문(박사) - 한국과학기술원 : 전산학과, 1994.8, [ ix, 135 p. ] | - |
dc.description.abstract | With the proliferation of massively parallel computers, the need for parallel execution of programs becomes apparent and essential. Nowadays, logic programming paradigm stands in the spotlight of numerous researchers, especially owing to potential parallelism inherent in logic programs. From the motives described above, interests in AND/OR-parallel evaluation of logic programs have been rapidly growing. Thus many algorithms have been proposed for AND/OR-parallel execution of logic programs. Nevertheless, they have still been in controversy from the viewpoint of completeness. This is caused by the "absence of really formalized model for AND parallelism." Therefore, we propose a formalization of AND-parallel execution of logic programs. The behavior of an execution method can be described in algebraic form. The algebraic specification is written in Milner``s Calculus of Communicating Systems. From this approach, we can prove the correctness of backward execution methods mathematically. For the purpose of easy construction of algebraic model, we introduce a new backward execution method called Path Model. The based models of the algebraic specification are followings: (1) Naive backtracking, (2) Chang``s semi-intelligent backtracking, (3) Path Model for intelligent backtracking. Since Path Model determines the actions of the backward execution in compile-time, it is appropriate for the algebraic specification. Furthermore the model gives small overhead to run-time determination of the actions. So the model can be implemented efficiently. To show the parctical efficiency, we propose an automation for an AND-process. Though the actions are determined in compile-time, we show that Path Model outperforms other backward execution models. The improvement comes from precise analysis of the AND-parallelism and the descriptive data structure of the principle of backward execution. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.title | (A) formalization of backward execution in parallel evaluation of logic programs | - |
dc.title.alternative | 논리 프로그램의 병렬 수행에서 후방향 수행의 정형화 | - |
dc.type | Thesis(Ph.D) | - |
dc.identifier.CNRN | 69678/325007 | - |
dc.description.department | 한국과학기술원 : 전산학과, | - |
dc.identifier.uid | 000875307 | - |
dc.contributor.localauthor | Choe, Kwang-Moo | - |
dc.contributor.localauthor | 최광무 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.