Rete 알고리즘의 병렬 및 분산 처리에 관한 기존 연구 분석

Ⅰ. 서 론

과거 생성 시스템(Production system) 혹은 규칙 기반 전문가 시스템(Rule-based expert system)에서 주로 사용되는 rete 알고리즘[1]이 최근 다시 관심을 받고 있다. 그 이유는 대량의 온톨로지 및 규칙을 위한 효율적 추론 방법이 되며[2], 또한 모든 분야에서의 지능적 서비스(Intelligent services)라는 현재 IT 패러다임과 관련이 있다고 할 수 있다.

현재 지능적 서비스의 핵심 기술은 딥러닝 즉 신경망, 그리고 GPU 병렬 컴퓨팅 및 빅 데이터와 같은 병렬 분산 처리 기술이다. 즉, 과거에는 상상 못했던 모든 상황의 데이터를 빅 데이터 기술로 수집하고, 이를 GPU 병렬 컴퓨팅 및 빅 데이터 기술을 이용하여 빠른 시간 안에 최적의 신경망으로 학습하는 것이다.

하지만 미래의 전 세계적으로 공유된 온톨로지(Globally shared ontologies)를 통한 지능적 서비스 및 지식 공유 서비스[3][4]에서는 지식의 표현 및 추론(Reasoning)을 위하여 신경망보다 더 나은 방법이 있다. 그것은 시맨틱 웹의 표준 규칙 언어인 RIF[5] 혹은 SWRL[6]의 IF-THEN의 지식 표현이며, 이러한 규칙을 rete 추론 알고리즘을 이용하여 효율적으로 추론할 수 있다.

최근 대량의 규칙 및 온톨로지 데이터를 추론하기 위하여 Hadoop 혹은 Spark와 같은 빅 데이터 기술을 활용해 보고자 하는 몇몇의 연구들[7]-[12]이 있다. 이러한 연구들을 분석해 보면 모든 연구들이 공통적으로 rete 알고리즘의 향상된 추론 성능을 제시하는 것을 확인할 수 있다. 따라서 본 논문에서는 과거 rete 알고리즘의 병렬 및 분산 처리로부터 현재의 빅 데이터 기술을 이용한 병렬 및 분산 처리까지 각 방법들이 어떤 측면에서 발전해 왔는지를 살펴보며, 대량의 규칙 및 온톨로지 데이터의 추론을 위하여 어떤 측면들이 고려되어야 하는지를 살펴본다.

이러한 rete 알고리즘에 대한 최근까지의 연구 내용에 대한 정리는 rete 알고리즘의 병렬 및 분산 처리 기술 개발에 관심 있는 연구자들에게 다른 시각에서의 참고자료로 활용될 수 있을 것이다.

1.1 몇 가지 전제

본 논문은 이전 연구[3][4]에서 소개된 RIF 규칙을 이용한 지식 공유 서비스에서의 규칙 추론 성능 향상과 관련된 연구이다. 우리는 그러한 서비스를 SRS(Shared Rules Service)라고 하였다.

그림 1은 SRS의 개념을 보여준다[3]. SRS에서는 사용자들이 공유된 온톨로지를 이용하여 자신들만의 지식을 RIF 규칙으로 표현하고, 이를 웹에 공유하여 다른 사용자들이 자신이 모르는 유용한 정보를 추론 하도록 하는 것이다.

Fig. 1.

Concept of SRS

예로, 그림에서 사용자의 프로파일, 즉 RDF 데이터는 그 사용자가 가입한 클라우드 추론 서비스에서 관리되고 있고, 사용자가 음식점에 들어설 경우 ②와 같이 음식점과 관련하여 다른 사용자들이 작성한 RIF 규칙이 해당 사용자의 추론 서비스로 전송되어 해당 사용자를 위한 유용한 정보를 추론한다. 또한 해당 사용자의 공개가 허용된 일부 프로파일 정보는 ②와 같이 동시에 음식점 추론 서비스로 전송되어 유용한 정보를 추론할 수 있다. 만약 해당 사용자가 특정 질병을 가지고 있다면 사용자가 몰랐던 음식에 대한 유용한 정보를 제공받을 수 있을 것이다.

이러한 공유된 규칙은 질병과 음식점이라는 문제 영역에서 뿐만이 아니라 우리 일상생활에서의 다양한 영역에 걸쳐 작성될 수 있으며, 따라서 개인이 제공받은 공유된 규칙의 수는 매우 클 수 있다. 따라서 대량의 규칙 및 온톨로지 데이터에 대한 가능한 신속하며 효율적인 추론이 요구된다.

1.2 RIF 규칙

SRS에서는 지식 공유를 위한 규칙 언어로 시맨틱 웹의 표준 규칙 언어인 RIF[5]를 고려한다. RIF는 크게 RIF-Core, RIF-BLD(Basic Logic Dialect), RIF-PRD(Production Rule Dialect)로 나누어진다. RIF-BLD는 혼 논리(Horn logic)와 일치하며, RIF- PRD는 생성 시스템의 특징을 갖는 규칙이며, RIF- Core는 RIF-BLD와 RIF-PRD의 공통부분을 정의한다. 본 연구에서는 기본적으로 RIF-BLD를 고려하며, 하지만 규칙의 조건들에 대한 부정(Negation) 그리고 결론에 여러 개의 assert문을 명세할 수 있는 RIF-PRD의 일부 특성을 함께 고려한다.

▪ 정의 1 (RDF 트리플 패턴) [3]

그림 2와 같이 RDF 그래프 G = (V, E)를 고려하자. v, u∈V는 노드를 나타내고, e∈E는 v와 u 사이의 에지를 나타낸다. RDF 트리플은 G에서의 [v, e, u]를 의미한다. v, e, u에 대해 각각 임의의 노드와 에지를 매칭한다는 의미로 변수 $x, $y, $z를 사용할 수 있다.

Fig. 2.

Graph representation of RDF data

SRS에서의 사용자 정의 지식은 어떤 RDF 온톨로지 데이터에 대하여 다음과 같이 RIF 규칙으로 표현될 수 있다: [$x, be, Vegetarian] ˄ [$x, beOn, Diet] → [$x, like, Salads]; [$x, like, chickenbreastsalad]. 이것은 $x가 채식주의자이며 다이어트 중이면 샐러드를 좋아하고 닭가슴살 샐러드를 좋아한다는 팩트(Fact)를 추론하는 RIF 규칙으로, 그림 2에서 [Park, like, Salads]와 [Park, like, chickenbreastsalad]의 새로운 팩트를 추론할 수 있다.

▪ 정의 2 (RIF 규칙에서의 조건과 추론 결과)

RIF 규칙은 왼편(LHS, Left-Hand Side)에 여러 가지 조건에 해당하는 RDF 트리플 패턴으로 구성되며, 오른편(RHS, Right-Hand Side)에는 추론 결과에 해당하는 트리플이 하나 혹은 여러 개 올 수 있다. 각 조건은 부정 연산(¬)이 적용될 수 있다.

본 논문의 구성은 다음과 같다. 2장에서는 rete 알고리즘을 간략히 소개한다. 3장에서는 과거 rete 알고리즘에 대한 병렬 및 분산 처리를 소개하며, 4장부터 6장까지는 최근의 Hadoop, Spark와 같은 빅 데이터 기술을 이용한 방법을 소개한다. 7장에서는 이러한 분석을 통해 rete 알고리즘의 효율적 병렬 및 분산 처리를 위해 고려해야 할 점들을 정리한다. 8장에서는 결론 및 향후 연구 내용을 기술한다.

Ⅱ. Rete 알고리즘

Rete 알고리즘은 생성 시스템에서 다수의 객체에 대한 효율적 패턴 매칭을 위하여 Forgy[1]에 의해 제안된 알고리즘이며, 현재 Drools, Clips, Jess와 같은 규칙 기반(Rule-based) 엔진에서 널리 사용되어 진다. 하지만 단일 컴퓨터에서 동작하는 rete 알고리즘이 처리하는 규칙 수가 100,000개가 될 경우 그 성능이 수 십 분으로 매우 안 좋아지며[4], 분명한 한계가 존재한다.

참고문헌 [13]에서 설명한 rete 알고리즘의 일반적 시간 복잡도는 O(n·m^k) 이며, 규칙의 수 n에 선형적(Linear)이며, 매칭되는 팩트의 수 m에 따른 다항식(Polynomial)을 갖는다. k는 모든 규칙 중 어떤 규칙이 갖는 LHS의 최대 조건수이다. 따라서 규칙의 수가 100,000개 보다 더 많아질 경우, 그리고 팩트 수의 증가에 따라 패턴 매칭의 시간이 더 커지는 것은 당연하며, 하지만 기하급수(Exponential)가 아니며 또한 SRS에서의 사용자 프로파일과 같은 팩트 수가 크지 않을 경우 병렬 및 분산 처리에 의한 성능 개선의 가능성이 높다.

그림 3은 rete 네트워크의 구성 및 기본 동작 원리를 보여준다. 그림 3은 참고문헌 [14]에서의 그림을 본 논문의 내용에 맞도록 수정한 것이다.

Fig. 3.

Example of rete network

· Rete 네트워크: 먼저 주어진 규칙들에 대하여 그림과 같은 rete 네트워크를 메모리에 구성한다.

· 작업 기억 메모리: 그림 3에 는 표현되지 않았지만 추론 과정 중 입력된 팩트들을 잠시 기억하는 메모리 장소이다. 따라서 단기 기억 메모리라고도 한다. 이후 이를 WM으로 표기하도록 하겠다.

· 알파 메모리: WM의 팩트들은 패턴 매칭을 통하여 해당 알파 메모리로 저장되고 WM으로 부터는 삭제된다. 그림에서는 각 RDF 트리플 패턴에 해당하는 알파 메모리가 존재함을 볼 수 있다. 예로, ‘AM for E1’은 RDF 트리플 패턴 [$x, hasDisease, renaldisease]에 매칭되는 팩트들을 저장하며, WM으로부터 [spiderman, hasDisease, renaldisease], [batman, hasDisease, renaldisease], [superman, hasDisease, reanaldisease], [ironman, hasDisease, reanaldisease]의 팩트들이 매칭되어 저장된 것이다. AM은 알파 메모리를 상징한다. 이후에도 새로운 팩트들이 WM으로 입력될 경우 패턴 매칭에 의하여 해당 패턴의 AM으로 저장되게 되고 WM으로부터는 삭제된다.

· 베타 메모리: 이것은 AND(˄) 연산에 대한 결과를 저장한다. 예로, ‘matches for E1 ˄ E2’는 [$x, hasDisease, renaldisease] ˄ [$x, eat, $z]의 매칭 결과를 저장한다. 따라서 ironman을 제외한 {[spiderman, hasDisease, renaldisease], [spiderman, eat, spinach]}, {[batman, hasDisease, renaldisease], [batman, eat, mugwort]}, {[superman, hasDisease, renaldisease], [superman, eat, spinach]}의 결과를 저장한다. 이것은 관계형 데이터 모델의 조인(Join) 연산과 같은 개념이다. 이후에는 베타 메모리를 BM으로 표기하도록 하겠다.

· 결과 노드(Conclusion node): C1, C2, C3, C4, C5의 규칙의 결과 노드들은 최종 매칭 결과로 저장되고, 또한 WM으로도 입력되어 반복적인 추론을 발생시킨다. 반복적인 추론의 예로, C2와 C3의 결과는 WM으로부터 E5에 매칭되어 ‘AM for E5’에 저장되고, E5를 포함하는 규칙 R4와 R5를 추론한다. rete 알고리즘은 더 이상의 추론이 발생되지 않을 때까지 위의 과정을 반복한다.

· 충돌 해결(Conflict resolution): 규칙 기반의 전문가 시스템에서는 어떤 입력이 주어질 경우 결과 노드를 통한 결과는 하나이어야 한다. 예로, 어떤 증상으로 인한 질병 진단 결과는 하나이어야 한다. 따라서 매칭된 여러 규칙 중 어떤 규칙이 실행(Rule firing)되어야 하는 지를 결정하는 것을 충돌 해결이라고 한다. 따라서 그림 3의 첫 번째 사이클(Cycle)에서 어떤 입력에 의해 규칙 R1, R2, R3가 매칭되었을 경우, 그리고 충돌 해결에 의해 R2가 결정되었을 경우, 추론 결과 C2는 다음 사이클의 ‘AM for E5’에 저장되게 된다.

▪ 관찰 2-1

이러한 rete 매칭이 빠른 이유는 1) AM과 BM을 계속 유지하므로 재계산을 피한다는 것이다. WM에 새로운 팩트가 입력될 경우 매칭되는 해당 AM 및 BM만 재계산된다. 2) 규칙들 사이에서의 같은 조건에 대하여 하나의 AM 혹은 BM만을 형성한다.

이러한 단일 컴퓨터에서의 rete 알고리즘의 성능을 개선하기 위한 과거의 연구들이 있으며, 예로 데이터베이스의 조인 순서 최적화 등을 고려한 TREAT[15], 해싱 인덱싱 등을 활용하는 rete/UL[14], 해싱 및 노드 인덱싱을 활용하는 T. Dong외 3인의 방법[16], 그리고 RETE*[17], D. Xiao외 3인의 방법[18] 등 많은 연구가 있다. 하지만 여전히 대량의 규칙과 팩트가 입력될 경우 단일 컴퓨터에서의 순차 처리(Sequential processing)는 성능 스케일 업에 한계가 있다.

따라서 rete 알고리즘을 다수의 프로세서 및 컴퓨터에서 수행하고자 하는 병렬 및 분산 처리에 대한 몇몇의 연구들이 이루어 졌으며, 다음 장들에서는 이러한 연구들을 소개한다.

Ⅲ. 과거의 병렬 및 분산 처리 연구

이미 과거에 병렬 및 분산 처리를 통한 생성 시스템의 성능 향상을 위한 몇몇 연구들이 수행되었다[19]. 비록 이러한 방법들이 Hadoop과 같이 모두에게 널리 알려진 일반적인 프레임워크에 기반하지 않고 각자의 특징적인 하드웨어 및 프레임워크를 갖지만, Hadoop 기반의 연구에서도 공통적으로 나타나는 rete 알고리즘을 병렬로 처리할 경우의 다양한 문제들을 이미 소개하고 있다.

당연히 과거에는 값싸지만 좋은 성능을 갖는 컴퓨터 수천 대를 빠른 네트워크 속도로 연결하는 하드웨어의 발전이 없었으므로, 각자의 특징적 하드웨어에 기반할 수밖에 없었을 것이고, 현재의 Hadoop과 같은 일반적 방법의 출현이 없었을 것이다.

각자의 특징적 하드웨어 구조는 주로 공유 메모리 멀티프로세서(Shared memory multiprocessor) 혹은 메시지 패싱(Message passing) 멀티프로세서 방식에 기반한다.

Hadoop 기반의 방법과 비교하여 Hadoop 또한 기본적으로 여러 컴퓨터 사이의 메시지 패싱이지만, 가장 큰 장점은 Hadoop 프레임워크를 이용하는 경우 과거에는 실험되지 못했던 수백 수천대의 컴퓨터로의 확장 시 신뢰성(Credibility)을 자동으로 제공받는 이점이 있다는 것이다. 하지만 Hadoop의 경우 맵 리듀스 기반의 구현을 따라야 하므로, 성능상의 제약사항이 존재할 수 있다. 우리는 이러한 것을 4장과 5장 Hadoop, Spark를 활용하는 방법에서 살펴본다.

3.1 Gupta외 4인의 방법

Gupta외 4인[20]은 16개의 CPU와 32 MByte의 공유 메모리를 가진 Encore Multimax 컴퓨터에서의 rete 알고리즘의 병렬처리를 구현하였다. 실험에 사용된 규칙의 수는 최대 637개로 우리의 가정과 비교하면 작다. 성능 개선은 그들의 실험에서 rete 알고리즘의 AM, BM 매칭 단계에서 2~11배까지의 성능 개선이 이루어짐을 보여준다. 병렬 처리의 단위는 그림 3에서 규칙 단위로 각 프로세서로 할당될 수 있으며, 예로 R1이 하나의 프로세서, R2와 R3가 하나의 프로세서, R4와 R5가 하나의 프로세서로 할당, 혹은 더 세밀한 병렬 처리(More fine-grained parallel processing)로 AM 매칭과 BM 조인 노드 단위로 분할될 수 있다[21]. 노드 단위의 분할은 Hadoop에서 소개할 그림 4의 Li외 4인의 방법과 유사하다.

Fig. 4.

Example of Hadoop based rete algorithm

▪ 관찰 3-1

Rete 알고리즘의 적절한 병렬 처리 단위가 고려될 필요가 있다.

참고문헌 [21]에서는 또한 RHS의 실행에 있어, 모든 매칭된 RHS가 구해질 때까지 충돌해결이 완료될 수 없으므로 궁극적으로 이것은 매칭은 병렬적이나 최종적으로 모든 규칙의 매칭이 완료될 때까지 기다릴 수밖에 없는 동기적(Synchronous) 순차(Sequential) 실행임을 지적하고 있다.

이러한 문제는 Hadoop을 이용하는 방법에서도 나타나며, rete 알고리즘 전체 시간의 90%는 LHS 매칭 단계에서 소모되고[22], 비록 RHS의 실행은 10%이나, 그 10%를 1%로 줄일 수 있음을 가정할 경우, 이러한 비동기적 특성은 이론적으로 최대 10배까지도 전체 시간을 지연시키는 것이다.

▪ 관찰 3-2

만약 충돌 해결을 고려하지 않을 경우 완전한 비동기적 병렬 처리가 고려될 필요가 있다. 여기서 완전함이란 전체의 실행을 의미한다.

Ⅳ. Hadoop 기반의 연구

Hadoop 프레임워크는 키 값에 따라 작업을 나누어 처리하는 맵(Map)과 이렇게 나누어 처리된 중간 결과를 다시 키 값에 따라 조합하는 리듀스(Reduce) 과정으로 구성되며, 맵의 결과는 HDFS(HaDoop File System)에 기록된다.

Ⅴ. Spark 기반의 연구

Hadoop 기반의 rete 분산 알고리즘의 문제점은 앞서 살펴본 바와 같이 맵 단계에서 중간 결과를 HDFS에 기록하여야 하는 것이며, 또한 추론 체인(Reasoning chain)의 경우 반복적인 맵-리듀스 작업이 비효율적이라는 것이다. 이러한 문제를 고려하여 최근에는 인메모리 기반의 분산 처리 프레임워크인 Spark를 활용한 rete 분산 알고리즘의 연구가 있으며, 몇 가지 연구에서는 Spark를 활용하는 것이 Hadoop을 사용하는 것보다 2 ~ 3 배의 개선 효과가 있는 것을 보여준다[12][28].

Spark에서는 메모리에서의 데이터 저장 관리를 위하여 RDD(Resilient Distributed Dataset)라는 객체를 사용할 수 있다. 이러한 RDD는 파티셔닝을 비롯하여 여러 가지 병렬 연산 기능을 제공한다.

5.1 Lee외 2인의 방법

Lee외 2인[12]은 Spark 기반의 rete 알고리즘을 소개하였으며, Wu와 4인의 Hadoop 기반의 방법[29]과 비교하여 최대 2.7배의 개선이 있음을 보여주고 있다. Lee의 방법에서는 먼저 주어진 규칙들에 대해 메타 테이블(Meta table)을 만드는 사전 준비 작업이 요구된다. 이러한 메타 테이블로는 Key-Value 테이블, Common Variable 테이블, Conclusion 테이블의 세 가지 테이블이 작성된다.

먼저 그림 5(a)는 그림 3에서의 규칙들에 대하여 만들어진 Key-Value 테이블이다. 각 조건의 predicate에 대하여, 공통 변수의 위치 정보를 기록한다. 예로, 규칙 R2의 조건 E1의 predicate은 hasDisease이며, subject 위치에 있는 $x는 E2의 $x와 공통 변수이다. R1의 경우 $x가 LHS의 조건 중에 공통 변수가 없으므로 기록되지 않는다.

Fig. 5.

Configuring meta tables

그림 5(b)는 Common Variable 테이블을 보여준다. Common Variable 테이블은 반복적인 맵 리듀스 과정에서 어떤 규칙의 다음 단계의 조건 평가를 위한 공통 변수의 위치 정보를 표현한다. 예로, R2의 경우 두 번째 단계의 공통 변수 매칭은 E2 조건의 subject의 위치에 있는 $x 변수이다. 세 번째 단계는 E2 조건의 object의 위치에 있는 $z 변수이고, 네 번째 단계는 E3 조건의 subject 위치에 있는 $z 변수이다.

그림 5(c)는 Conclusion 테이블을 보여준다. Conclusion 테이블은 추론 결과의 새로운 트리플을 생성하기 위해 사용되어 진다. 예로, R2는 E2의 $x를 subject, beCareful을 predicate, E3의 $z를 object로 하는 새로운 트리플을 추론한다.

n개의 주어진 규칙으로부터 이러한 Key-Value 테이블, Common Variable 테이블, Conclusion 테이블의 구축은 모든 규칙에서의 LHS의 조건의 수가 그렇게 크지 않다고 가정할 경우 시간 복잡도는 O(n)으로 그렇게 많은 비용을 요구하지 않는다.

HDFS에 저장되는 사용자 프로파일은 전처리 과정을 통하여 key-value 형태로 변환되어 저장된다. 이를 위해 Key-Value 테이블을 참조한다. 예로, 트리플 [spiderman, hasDisease, reanldisease]의 경우 그림 5(a)의 Key-Value 테이블에서 term hasDisease에 대하여 <(R2, spiderman), {[spiderman, hasDisease, renaldisease]}>, <(R3, spiderman), {[spiderman, hasDisease, renaldisease]}>, <(R4, spiderman), {[spiderman, hasDisease, renaldisease]}>, <(R5, spiderman), {[spiderman, hasDisease, renaldisease]}> 의 4개의 변환된 데이터로 저장된다. 하지만 공통 변수가 없는 조건이 하나인 R1 규칙에 대하여서도 <(R1, spiderman), {[spiderman, hasDisease, renaldisease]}>가 만들어 져야 하며, 그러나 논문에서는 이러한 부분에 대한 설명이 없다. 다음으로 [spiderman, eat, spinach]에 대하여, term eat에 대하여 <(R2, spiderman), {[spiderman, eat, spinach]}>, <(R2, spinach), {[spiderman, eat, spinach]}>, <(R3, spiderman), {[spiderman, eat, spinach]}>, <(R3, spinach), {[spiderman, eat, spinach]}>의 4개의 변환된 데이터로 저장된다.

중요한 것은 이러한 변환된 데이터들은 키 값을 기준으로 Spark의 Hash Partitioner를 통해 클러스터의 각 노드에 파티셔닝(Partitioning)된다는 것이다. 따라서 데이터는 각 노드에 고르게 분포되며, 그림 3에서의 베타 조인을 위한 두 트리플은 같은 노드에 존재하게 된다. 예로, <(R2, spiderman), {[spiderman, hasDisease, renaldisease]}>와 <(R2, spiderman), {[spiderman, eat, spinach]}>는 같은 노드에 존재할 것이다. 하지만 Lee는 어떤 규칙의 모든 변환된 데이터가 같은 노드에 존재하여 셔플링이 발생하지 않는다고 하였는데, 이것은 의문이다. 왜냐하면 <(R2, spinach), {[spiderman, eat, spinach]}>의 경우 키 (R2, spinach)는 해시 값이 다를 것이므로 다른 노드에 할당될 것이고, R2의 세 번째 단계를 평가하기 위하여 셔플링은 발생할 수밖에 없다.

규칙 및 데이터의 전처리 과정 후 진행되는 맵 리듀스 기반의 추론 알고리즘의 동작 원리는 그림 6과 같다.

Fig. 6.

Example of spark based rete algorithm

추론 과정은 리듀스 → 맵 → 리듀스 → ... → 맵 → 리듀스를 반복하며, 그림 5(b)의 Common Variable 테이블에서의 마지막 단계가 끝난 규칙들에 대해서는 그림 5(c)의 Conclusion 테이블에 의하여 결론을 추론한다. 데이터의 전처리 과정이 이미 되어 있으므로 첫 번째 사이클에서는 맵 과정 없이 리듀스 과정을 바로 수행한다.

먼저 그림 6(a)의 R1의 경우 전처리 과정에서 Node1의 RDD에 저장된 <(R1, spiderman), {[spiderman, hasDisease, renaldisease]}>에 대하여, 맵 과정 없이, 리듀스 과정을 거친 후, 그림 5(b)의 Common Variable 테이블에서 R1의 2단계가 없으므로 바로 그림 5(C)의 Conclusion 테이블을 참조하여 [spinach, beBadFor, spiderman]의 새로운 트리플을 추론하다.

또한 Node2의 RDD에 저장된 <(R2, spinach), {[spiderman, eat, spinach]}>, <(R2, spinach), {[spinach, rdf:type, vegetables]}>는 reduce 과정에서 키 (R2, spinach)에 의해 <(R2, spinach), {[spiderman, eat, spinach], [spinach, rdf:type, vegetables]}>로 그룹화 된다. Node3에서도 <(R2, spiderman), {[spiderman, hasDisease, renaldisease]}>와 <(R2, spiderman), {[spiderman, eat, spinach]}>는 키 (R2, spiderman)에 의해 <(R2, spiderman), {[spiderman, hasDisease, renaldisease], [spiderman, eat, spinach]}>로 그룹화 된다. 여기서 주목할 것은 각 데이터가 키 값에 의해 같은 노드에 해시 파티셔닝 되었으므로, 맵리듀스의 한 사이클에서 리듀스 과정의 그룹화를 위해 셔플링이 발생하지 않고 각 노드 내에서 처리된다는 것이다.

그림 6(b)의 두 번째 사이클의 맵 단계에서는 첫 번째 사이클의 추론 결과의 키를 Common Variable 테이블을 참조하여 다음 단계의 공통 인자로 치환한다. 예로, <(R2, spiderman), {[spiderman, hasDisease, renaldisease], [spiderman, eat, spinach]}>의 3단계는 (eat, object)이므로, spiderman → spinach에 의해, <(R2, spinach), {[spiderman, hasDisease, renaldisease], [spiderman, eat, spinach]}>가 된다. 이러한 맵 단계에서의 키 변경은 그림 6(b)에서와 같이 Hash Partitioner에 의해 해당 노드로 이동시키는 셔플링이 발생한다.

Ⅵ. GPU 기반의 연구

최근 딥 러닝과 관련하여 GPU 기반의 고성능 병렬 프로그래밍 기술이 활용되고 있다. Peters외 3인[30]은 단일 컴퓨터에서의 GPU 기반의 rete 알고리즘의 병렬 처리에 대한 연구를 소개하고 있다.

병렬 프로그래밍 방법으로는 OpenCL[31]을 사용한다. OpenCL에서 문자열(String)은 처리에 효율적이지 않으므로, subject, predicate, object에 대한 문자열 값을 정수 값으로 맵핑하고 이러한 정수 값을 참조하여 사용한다.

GPU에서의 각 쓰레드는 하나의 RDF 트리플당 수행되며, 그림 3에서 그 RDF 트리플이 어떤 AM에 매칭 되는지를 병렬로 수행한다. 따라서 RDF 트리플 수만큼의 쓰레드가 수행된다. 또한 베타 조인 노드에 대해서는 그림 7과 같이 두 입력되는 AM에 대하여, 어느 한 쪽의 AM의 팩트에 대하여 다른 한 쪽 AM의 모든 팩트들을 매칭하는 쓰레드가 실행된다. 따라서 왼쪽의 AM의 팩트의 수가 4개이므로 4개의 쓰레드가 수행된다.

Fig. 7.

Example of parallel processing using GPU

따라서 그림 3의 전체 rete 네트워크상에서의 병렬 수행은 먼저 WM의 각 RDF 트리플의 AM 매칭이 병렬적으로 수행이 되고, 모든 RDF 트리플의 AM 매칭이 끝났을 경우 앞서 설명한 베타 조인 노드들에서의 병렬 수행이 이루어진다.

또한 그림 3에서 E1 ˄ E2와 E1 ˄ E2 ˄ E3는 순차적으로 수행되나, E1 ˄ E2 ˄ E3와 E1 ˄ E2 ˄ E4는 병렬로 수행된다. 그들의 실험에서는 비록 GPU가 아닌 CPU에서 코어수를 증가시키며 수행한 실험을 보여주었지만, 1개 코어에 비해 6개 코어를 사용할 경우 5 ~ 6배의 성능 향상이 이루어짐을 보여준다.

Ⅶ. Rete 알고리즘의 병렬 및 분산 처리시의 고려 사항

표 1은 지금까지의 내용을 토대로 rete 알고리즘의 병렬 및 분산 처리 시에 고려해야할 사항들을 정리한 것이다. 앞서 이야기한 대로 이러한 사항들은 과거의 연구에서도 고려된 사항들이지만, 현재는 수백 수천대의 컴퓨터를 안전하게 병렬 및 분산 처리할 수 있는 Hadoop 프레임워크를 활용할 수 있다.

Table 1.

Considerations in parallel and distributed processing of the rete algorithm

본 논문에서 고려하는 SRS 규칙 추론의 특성은 1) 대량의 규칙 및 온톨로지 데이터를 가능한 신속히 추론해야 하며 2) 연속적으로 유입되는 규칙 및 온톨로지 데이터를 추론할 수 있어야 하는 것이다.

두 번째의 연속적으로 유입되는 규칙 처리라는 것은 기존의 규칙들에 대하여 만들어진 rete 네트워크를 규칙이 유입될 때마다 동적으로 재구성하여 앞으로 유입될 데이터뿐만 아니라 이전 온톨로지 데이터에 대해서도 평가를 수행할 수 있어야 함을 의미한다. 앞서 살펴본 과거 및 기존 연구들은 이러한 특성을 구체적으로 고려하지 않았으며, SRS에서는 이러한 특성을 고려하여 설계할 필요가 있다.

Ⅷ. 결론 및 향후 연구 내용

본 논문에서는 rete 알고리즘의 병렬 및 분산 처리에 대한 과거로부터 현재까지의 연구 내용을 정리 분석하였다. 또한 이러한 분석을 통하여 향후 rete 알고리즘을 개발할 경우의 고려 사항 등을 정리하였다. 이러한 병렬 및 분산 처리를 통한 성능이 개선된 rete 알고리즘은 서론에서 언급한 것처럼 향후 규칙을 통한 지능적 서비스 및 지식 공유 서비스에 활용될 가능성이 높다.

향후 연구 계획은 본 논문의 분석을 토대로 실제적으로 활용 가능한 rete 알고리즘의 신속하며 효율적인 병렬 및 분산 처리 방법을 개발하는 것이다. 마지막으로 본 논문에서는 rete 알고리즘의 병렬 및 분산 처리에 대한 현재까지의 모든 연구를 가능한 조사하려고 하였으며, 이러한 정리가 관련 연구자들에게 다른 시각에서의 참고자료로 활용될 수 있길 바란다.

Acknowledgments

이 논문은 2018년도 정부(교육부)의 재원으로 한국연구재단의 지원을 받아 수행된 기초연구사업임. (No. 2016R1D1A1B03930564).

References

• C. L. Forgy, "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", Artificial Intelligence, 19(1), p17-37, Sep.), (1982. [https://doi.org/10.1016/0004-3702(82)90020-0]
• J. Choi, and Y. Park, "Research Trends in Ontology Reasoning", Communications of KIISE, 24(12), p47-55, Dec.), (2006.
• J. Kim, "An Analysis of Uncertainty Problems in Knowledge Sharing Service Using RIF Rules", Journal of KIIT, 16(9), p1-11, Sep. Sep.), (2018. [https://doi.org/10.14801/jkiit.2018.16.9.1]
• J. Kim, and H. Seo, "Shared Rules: Knowledge Sharing Service by RIF Rules", IEEE BigComp 2019, p156-159, Feb.), (2019. [https://doi.org/10.1109/bigcomp.2019.8679451]
• RIF Overview, http://www.w3.org/TR/2010/NOTE-rif-overview-20100622/ [accessed: Apr. 16, 2019].
• SWRL: A Semantic Web Rule Language Combining OWL and RuleML, http://www.w3.org/Submission/SWRL [accessed: Apr. 16, 2019].
• Y. Li, W. Liu, B. Cao, J. Yin, and M. Yao, "An Efficient MapReduce-based Rule Matching Method for Production System", Future Generation Computer Systems, 54, p478-489, Jan.), (2016. [https://doi.org/10.1016/j.future.2015.03.010]
• R. Maeda, N. Ohta, and K. Kuwabara, "MapReduce-based Implementation of a Rule System", Studies in Computational Intelligence, 513, p197-206, (2014).
• J. Urbani, S. Kotoulas, J. Maassen, F. V. Harmelen, and H. Bal, "WebPIE: A Web-scale Parallel Inference Engine using MapReduce", Journal of Web Semantics, 10, p59-75, Jan.), (2012. [https://doi.org/10.1016/j.websem.2011.05.004]
• J. Urbani, S. Kotoulas, J. Maassen, F. V. Harmelen, and H. Bal, "OWL Reasoning with WebPIE: Calculating the Closure of 100 Billion Triples", Lecture Notes in Computer Science, 6088, p213-227, Jan.), (2010.
• S. Zhu, H. Huang, and L. Zhang, "A Distributed Architecture for Rule Engine to Deal with Big Data", ICACT 2016, p602-606, Jan.), (2016. [https://doi.org/10.1109/icact.2016.7423487]
• W. Lee, S. Bae, and Y. Park, "A Study on Distributed Parallel SWRL Inference in an In-Memory-Based Cluster Environment", Journal of KIISE, 45(3), p224-233, Mar.), (2018. [https://doi.org/10.5626/jok.2018.45.3.224]
• L. Albert, "Average Case Complexity Analysis of RETE Pattern-Match Algorithm and Average Size of Join in Databases", INRIA Research Report, (1989). [https://doi.org/10.1007/3-540-52048-1_46]
• R. B. Doorenbos, "Production Matching for Large Learning Systems", Doctoral Dissertation, Carnegie Mellon University, (1995).
• P. Nayak, A. Gupta, and P. Rosenblum, "Comparison of the Rete an Treat Production Matchers for Soar (A Summary)", Proc. of AAAI-88, p693-698, (1988).
• T. Dong, J. Shi, J. Fan, and L. Zhang, "An Improved Rete Algorithm Based on Double Hash Filter and Node Indexing for Distributed Rule Engine", IEICE trans. on Information and Systems, E96-D(12), p2635-2644, Dec.), (2013. [https://doi.org/10.1587/transinf.e96.d.2635]
• I. Wright, and J. Marshall, "The Execution Kernel of RC++: RETE*, A Faster Rete with Treat as A Special Case", Int. J. of Intelligent Games and Simulation, 2(1), p36-48, Feb.), (2003.
• D. Xiao, Y. Tong, H. Yang, and M. Cao, "The Improvement for Rete Algorithm", Proc. of the 2009 First IEEE Int. Conf. on Information Science and Engineering, p5222-5225, Dec.), (2009. [https://doi.org/10.1109/icise.2009.1221]
• S. Kuo, and D. Moldovan, "The State of Art in Parallel Production Systems", Journal of Parallel and Distributed Computing, 15(1), p1-26, May), (1992.
• A. Gupta, C. L. Forgy, D. Kalp, A. Newell, and M. Tambe, "Parallel OPS5 on the Encore Multimax", Proc. of 1988 Int. Conf. on Parallel Processing, Aug.), (1988.
• H. G. Okuna, and A. Gupta, "Parallel Execution of OPS5 in QLISP", Proc. of The Fourth Conf. on Artificial Intelligence Applications, Mar.), (1988.
• T. Ishida, "Parallel, Distributed and Multiagent Production Systems", Proc. of the First Int. Conf. on Multi-Agent Systems, p416-422, (1995). [https://doi.org/10.1007/3-540-58698-9]
• A. Acharya, and M. Tambe, "Production Systems on Message Passing Computers: Simulation Results and Analysis", Proc. of 1989 Int. Conf. on Parallel Processing, (1989).
• A. Gupta, and M. Tambe, "Suitability of Message Passing Computers for Implementing Production Systems", Proc. of AAAI-88, Aug.), (1988. [https://doi.org/10.21236/ada207321]
• J. Bein, and R. King, "MOBY: An Architecture for Distributed Expert Database Systems", Proc. of the 13th VLDB, p13-20, (1987).
• S. J. Stolfo, "Five Parallel Algorithms For Production System Execution on the DADO Machine", Proc. of AAAI-84, p300-307, Aug.), (1984.
• M. A. Kelly, and R. E. Seviora, "An Evaluation of DRete on CUPID for OPS5 Matching", Proc. of the 11th Int. Joint Conf. on Artificial intelligence, p84-90, Aug.), (1989.
• W. Lee, S. Bang, and Y. Park, "Large Scale Incremental Reasoning Using SWRL Rules in a Distributed Framework", Jornal of KIISE, 44(4), p383-391, Apr.), (2017. [https://doi.org/10.5626/jok.2017.44.4.383]
• H. Wu, J. Liu, D. Ye, J. Wei, and H. Zhong, "Scalable Horn-Like Rule Inference of Semantic Data Using MapReduce", Int. Conf. on Knowledge Science, Engineering and Management, p270-277, (2014). [https://doi.org/10.1007/978-3-319-12096-6_24]
• M. Peters, C. Brink, S. Sachweh, and A. Zündorf, "Rule-based Reasoning on Massively Parallel Hardware", Proc. of the 9th Int. Conf. on Scalable Semantic Web Knowledge Base Systems, p33-48, (2013).
• OpenCL, https://www.khronos.org/opencl [accessed: Apr. 16, 2019].