[논문]인간 기억 인출 과정을 응용하여 설계된 ACT-R 기반 페이지 교체 정책

노홍찬; 박상현

doi:10.3745/kipstd.2011.18d.1.001

문제 정의

이러한 새로운 활성도 값을 기반으로 하는 페이지 교체 알고리즘을 ACTR이라 하고 이를 바탕으로 데이터베이스 버퍼 캐쉬에서 페이지 교체를 수행하는 실험을 수행해보았다.
ACT-R[4]에서 사용하는 지식의 기본 단위인 chunk를 데이터베이스 기술에 적용하여 자주 같이 접근되는 페이지들을 ACT-R의 activation level 이론에 근거하여 chunk로 묶고 prefetching 단위나 페이지 재배치 정책에 chunk 개념을 활용하는 등의 연구가 이루어질 수 있다. 이러한 향후 연구들을 수행하여, 현재 컴퓨터과학의 인공지능 분야에 많이 활용되고 있는 인지과학적 지식들을, 현재는 그 적용이 거의 전무한 상태인 데이터베이스 분야의 기술들에도 활용하여, 데이터베이스 시스템 관련 기술의 발전에 새로운 계기를 제공하고자 한다.
이에 본 연구에서는 ACT-R의 base-level activation의 접근방법을 캐쉬 페이지 교체 정책에 적용하여 인간의 기억 메커니즘과 유사하면서도 기존 페이지 교체 알고리즘들보다 효율적인 페이지 교체 정책을 제안하고자 한다. Base-level activation에서 제안된 frequency, recency, spacing 효과 모두를 고려한 수식을 페이지 교체 알고리즘의 교체 기준이 되는 척도로 변형하여 적용하며 기존의 LRFU의 문제인 recency 효과와 관련된 지수 함수(exponential function)를 ACT-R에서처럼 멱함수 (power function)로 적용하여 페이지 교체 알고리즘을 설계하고 이를 실제 데이터베이스 환경에서의 workload를 이용하여 실험 해보려고 한다.

가설 설정

특이하게도, LRFU의 개별 페이지에 대한 활성도 함수와 ACT-R의 개별 기억에 대한 활성도 함수인 식(1)과 식(4)가 각각 지수 함수와 멱함수로 다른 것을 제외하고는 거의 일치한다. LRFU가 현재까지 가장 효율적으로 동작하는 페이지 교체 알고리즘인 것을 고려할 때 이러한 둘 간의 유사성은 [5]에서의 Anderson의 가정을 되돌아보게 한다. Anderson의 가정처럼 인간은 환경적인 조건을 인간의 기억 모델에 최적으로 반영했을 때 환경에 가장 최적으로 반응할 수 있으며, 이와 마찬가지로 컴퓨터의 경우에도 역시 환경적인 조건을 제대로 반영하게 되면 가장 효율적인 페이지 교체 정책이 설계될 수 있다.

제안 방법

이에 본 연구에서는 ACT-R의 base-level activation의 접근방법을 캐쉬 페이지 교체 정책에 적용하여 인간의 기억 메커니즘과 유사하면서도 기존 페이지 교체 알고리즘들보다 효율적인 페이지 교체 정책을 제안하고자 한다. Base-level activation에서 제안된 frequency, recency, spacing 효과 모두를 고려한 수식을 페이지 교체 알고리즘의 교체 기준이 되는 척도로 변형하여 적용하며 기존의 LRFU의 문제인 recency 효과와 관련된 지수 함수(exponential function)를 ACT-R에서처럼 멱함수 (power function)로 적용하여 페이지 교체 알고리즘을 설계하고 이를 실제 데이터베이스 환경에서의 workload를 이용하여 실험 해보려고 한다.
본 연구에서는 인간의 기억 인출 과정에서의 과거 해당 기억에 대한 인출 기록들의 recency와 빈도가 인출 확률에 영향을 미치는 관계를 분석한 기존의 인지과학 분야의 연구 결과를 활용하였다. 해당 연구에서 recency 효과가 지수함수 형태가 아닌 멱함수의 형태로 감소한다는 것을 밝혀낸 것을 페이지 교체 정책 설계에 적용하여 ACTR을 제안하였다.
전체 트레이스에서 약 30만개의 읽기 작업을 추출해냈다. 이렇게 얻은 디스크 접근 데이터를 기반으로, 제안하는 페이지 교체 정책인 ACTR과 비교하고자 하는 페이지 교체 정책들인 LRFU, LRU, LFU에 대해서 시뮬레이션 기반으로 실험을 진행하였고 hit ratio를 측정해보았다.
인간 기억의 유지 비율(P)을 시간(T)에 따라 실제 측정한 실험 결과를 이용하여 P를 각각 T에 대한 지수함수와 멱함수를 표현해보고 얼마나 두 함수가 실제 실험결과에 잘 맞는가를 비교해본 것이다. 이를 위해 지수 함수와 멱함수 가정에 의해 P를 T에 대한 수식으로 나타낸 후, 양 변에 log를 취해보았다. 지수함수의 경우, 그 결과로 logP와 T간에 선형적인 관계가 성립해야하므로 실험결과에서 P만을 log scale로 변형해서 다시 그래프를 그려보았다.
이는 (그림 2)에 잘 나타나 있다. 인간 기억의 유지 비율(P)을 시간(T)에 따라 실제 측정한 실험 결과를 이용하여 P를 각각 T에 대한 지수함수와 멱함수를 표현해보고 얼마나 두 함수가 실제 실험결과에 잘 맞는가를 비교해본 것이다. 이를 위해 지수 함수와 멱함수 가정에 의해 P를 T에 대한 수식으로 나타낸 후, 양 변에 log를 취해보았다.
이를 위해 지수 함수와 멱함수 가정에 의해 P를 T에 대한 수식으로 나타낸 후, 양 변에 log를 취해보았다. 지수함수의 경우, 그 결과로 logP와 T간에 선형적인 관계가 성립해야하므로 실험결과에서 P만을 log scale로 변형해서 다시 그래프를 그려보았다. 그 결과 변형된 그래프는 (그림 2)의 가운데 그래프처럼 예상과 달리 선형적이지 않은 결과가 나왔다.
이러한 이유로 LRFU는 LRU와 LFU의 특징을 모두 반영하여 접근의 recency와 frequency를 모두 고려한 페이지 교체 알고리즘을 제안하였다. 페이지 교체 대상을 선정하기 위해 다음과 같은 식에 의해 개별 페이지의 활성도를 계산하고 그 활성도가 가장 낮은 페이지를 캐쉬에서 쫓아내는 방식을 취하였다.
본 연구에서는 인간의 기억 인출 과정에서의 과거 해당 기억에 대한 인출 기록들의 recency와 빈도가 인출 확률에 영향을 미치는 관계를 분석한 기존의 인지과학 분야의 연구 결과를 활용하였다. 해당 연구에서 recency 효과가 지수함수 형태가 아닌 멱함수의 형태로 감소한다는 것을 밝혀낸 것을 페이지 교체 정책 설계에 적용하여 ACTR을 제안하였다. 또한 실험을 통해 제안한 ACTR의 성능이 기존에 데이터베이스 버퍼 캐쉬에서 가장 좋은 성능을 보이는 것으로 알려진 LRFU보다 우수한 성능을 보인다는 것을 입증하였다.

대상 데이터

실험을 위해 workload로서 OLTP(OnLine Transaction Processing) 데이터베이스 환경에서 대표적 벤치마크인 TPC-C[6]를 선택하였으며, MYSQL 데이터베이스를 사용하여 트레이스 기반 시뮬레이션 실험을 진행하였다. TPC-C 생성 대표적인 공개 소스 툴인 HAMMERORA [8]를 사용하여 TPC-C 입력 파라미터로서 다음 항목들을 사용하였다(SCALE FACTOR: 1, 사용자 수: 10, 사용자당 트랜잭션 수: 1000개).
MYSQL의 경우 데이터베이스의 버퍼의 간섭을 최소화한 트레이스를 얻기 위해 버퍼 풀 (buffer pool) 크기를 최소 크기인 1MB로 설정한 후 트레이스를 수집하였다. 트레이스는 DiskMon [7]툴을 사용하여 저장장치 드라이버 수준에서 저장장치에 대한 읽기, 쓰기 작업에 대해 모두 수집하였다. 전체 트레이스에서 약 30만개의 읽기 작업을 추출해냈다.

이론/모형

실험을 위해 workload로서 OLTP(OnLine Transaction Processing) 데이터베이스 환경에서 대표적 벤치마크인 TPC-C[6]를 선택하였으며, MYSQL 데이터베이스를 사용하여 트레이스 기반 시뮬레이션 실험을 진행하였다. TPC-C 생성 대표적인 공개 소스 툴인 HAMMERORA [8]를 사용하여 TPC-C 입력 파라미터로서 다음 항목들을 사용하였다(SCALE FACTOR: 1, 사용자 수: 10, 사용자당 트랜잭션 수: 1000개). MYSQL의 경우 데이터베이스의 버퍼의 간섭을 최소화한 트레이스를 얻기 위해 버퍼 풀 (buffer pool) 크기를 최소 크기인 1MB로 설정한 후 트레이스를 수집하였다.
Anderson은 [4]에서 인간의 장기 기억 중 서술 기억(declarative memory)을 인출하는 데 있어서 사용되는 activation level 공식을 많은 응용 연구들에서 가장 성공적으로 검증된 이론이라고 언급하였다. 이러한 activation level은 서술 기억의 인출 과정에 있어 기억 인출 속도와 확률을 결정하며 이 이론을 구성하는 핵심 요소인 base-level activation 이론은 Anderson이 1991년에 발표한 [5]에 근거한다.

성능/효과

또한 실험을 통해 제안한 ACTR의 성능이 기존에 데이터베이스 버퍼 캐쉬에서 가장 좋은 성능을 보이는 것으로 알려진 LRFU보다 우수한 성능을 보인다는 것을 입증하였다. ACTR은 LRFU에 비해 파라미터 값에 관계없이 성능이 우수하며 최대 약 8% 정도의 성능 이점을 가지는 것으로 드러났다. 이러한 결과는 본 논문에서 제안하는 새로운 페이지 교체 정책인 ACTR이 기존의 단순한 LRU나 LFU와 같은 페이지 교체 정책보다 페이지 교체 시에 계산 시간이 더 소모되지만, CPU cache에 비해 상대적으로 연산 시간보다는 I/O 수행 시간이 중요한 DBMS cache에서 적용되어 DBMS의 성능을 개선할 수 있음을 시사한다.
캐쉬 크기에 비례하여 모든 알고리즘들이 일정하게 성능이 증가하였으며, 캐쉬 크기에 관계없이 제안하는 ACTR이 타 캐쉬 알고리즘들에 비해 가장 좋은 hit ratio를 보였다. ACTR은 TPC-C 워크로드에 있어 전체 DBMS 크기의 5%～6%에 해당하는 DBMS cache를 사용했을 때, LFRU, LRU, LFU 각각에 대해서 평균적으로 3.17%, 14.71%, 3.77% 성능 향상을 보이는 것으로 나타났다. 이러한 ACTR 페이지 교체 정책의 성능 우위가 DBMS 캐쉬 크기 변화에 따라 계속 유지되는 것을 보였다.
ACTR은 k 값이 40 이상일 때에 대해서는 큰 변화 폭을 보이지 않았으며 k 값이 60일 때 접근 시간의 리스트를 기록하기 위한 추가적인 메모리 공간을 최소화시키면서도 성능이 최적에 근접한 실험 결과를 보였다.
LRFU는 데이터베이스에서 수행되는 워크로드의 특성을 분석해본 결과, 특정 페이지가 다시 접근될 확률은 과거 해당 페이지에 대한 접근의 recency 또는 frequency와 연관이 있지만 그 영향 크기가 캐쉬에 할당된 메모리의 크기에 따라 동적으로 변한다는 사실을 밝혀냈다. 이러한 사실을 기반으로 접근의 recency만을 고려한 LRU 또는 접근의 frequency만을 고려한 LFU는 최적의 페이지 교체 알고리즘이 될 수 없다고 주장하였다.
LRFU의 경우 λ에 비해 매우 민감하게 성능이 변화하였으며 최대 성능과 최소 성능의 변동 폭이 약 13%까지 벌어지는 결과를 보였다.
먼저 Anderson은 인간이 환경적인 조건에 최적으로 반응하도록 여러 세대를 거쳐서 진화했다고 가정하며, 그러므로 인간의 기억 인출 및 저장 과정을 알아보기 위해서는 인간의 기억에 영향을 미치는 환경적인 조건이 어떠한가를 분석해봐야 한다고 주장하였다. 그리하여 환경적인 조건을 분석해본 결과 최근에 접근된 객체일수록 그리고 자주 접근된 객체일수록 향후에 다시 접근될 확률이 높다는 것을 여러 실험을 통해서 밝혀내었다. 또한 그러한 recency 효과가 시간에 따라 멱함수의 형태로 감소한다는 것, 그리고 frequency 효과는 단순히 그러한 recency 효과를 더하는 효과만이 있다는 것을 밝혀내었다.
그와 반대로 ACTR의 경우 상대적으로 LRFU에 비해 λ에 덜 민감하게 성능이 변화하였으며 최대 변동 폭이 약 8%로 나타났다.
더불어, 기존의 연구자들이 기억의 recency 효과에 대해서 recency 효과가 감소하는 비율이 기억의 마지막 인출 시간으로부터 지수함수와 유사하게 감소한다는 주장을 했던 것에 대해서 지수함수가 아니라 멱함수에 더 가깝게 감소한다는 사실을 밝혀내었다. 이는 (그림 2)에 잘 나타나 있다.
또한 ACTR은 λ값에 상관없이 LRFU에 비해서 좋은 성능을 나타내었고 최대의 성능 차이는 약 8% 정도로 나타났다.
또한 recency와 frequency를 실제로 반영하는 측면에서 두 함수를 비교해 볼 때에도 지수함수보다는 멱함수가 두 성질 모두를 더 잘 반영해주는 것을 알 수 있다. (그림 3)은 지수 함수와 멱함수를 비교한 것이다.
그리하여 환경적인 조건을 분석해본 결과 최근에 접근된 객체일수록 그리고 자주 접근된 객체일수록 향후에 다시 접근될 확률이 높다는 것을 여러 실험을 통해서 밝혀내었다. 또한 그러한 recency 효과가 시간에 따라 멱함수의 형태로 감소한다는 것, 그리고 frequency 효과는 단순히 그러한 recency 효과를 더하는 효과만이 있다는 것을 밝혀내었다.
해당 연구에서 recency 효과가 지수함수 형태가 아닌 멱함수의 형태로 감소한다는 것을 밝혀낸 것을 페이지 교체 정책 설계에 적용하여 ACTR을 제안하였다. 또한 실험을 통해 제안한 ACTR의 성능이 기존에 데이터베이스 버퍼 캐쉬에서 가장 좋은 성능을 보이는 것으로 알려진 LRFU보다 우수한 성능을 보인다는 것을 입증하였다. ACTR은 LRFU에 비해 파라미터 값에 관계없이 성능이 우수하며 최대 약 8% 정도의 성능 이점을 가지는 것으로 드러났다.
이를 토대로 Anderson은 지수함수 가정이 틀렸음을 설명하였다. 반대로 멱함수의 경우 log를 양변에 취한 수식에 의해 logP와 logT의 선형적인 관계가 형성되어야 하는데, 실험결과의 P와 T 모두를 log scale로 변형하여 나타내본 결과, (그림 2)의 가장 오른쪽 그림처럼 선형적인 성질이 근사하게 나타남을 확인할 수 있었다. 이를 근거로 Anderson은 인간 기억의 recency 효과가 지수함수가 아닌 멱함수 성질을 가진다는 사실을 밝혀냈다.
이러한 ACTR 페이지 교체 정책의 성능 우위가 DBMS 캐쉬 크기 변화에 따라 계속 유지되는 것을 보였다. 본 실험에서 기존에 DBMS cache에서 가장 좋은 성능을 보이는 것으로 알려진 LRFU가 LFU에 비해서 DBMS cache 크기와 상관없이 평균적으로 1.02%의 hit ratio 성능 우위를 가진데 비해, ACTR의 경우는 LRFU에 비해 2.68%, LFU에 비해 3.7%의 성능 우위를 가진다.
77% 성능 향상을 보이는 것으로 나타났다. 이러한 ACTR 페이지 교체 정책의 성능 우위가 DBMS 캐쉬 크기 변화에 따라 계속 유지되는 것을 보였다. 본 실험에서 기존에 DBMS cache에서 가장 좋은 성능을 보이는 것으로 알려진 LRFU가 LFU에 비해서 DBMS cache 크기와 상관없이 평균적으로 1.
ACTR은 LRFU에 비해 파라미터 값에 관계없이 성능이 우수하며 최대 약 8% 정도의 성능 이점을 가지는 것으로 드러났다. 이러한 결과는 본 논문에서 제안하는 새로운 페이지 교체 정책인 ACTR이 기존의 단순한 LRU나 LFU와 같은 페이지 교체 정책보다 페이지 교체 시에 계산 시간이 더 소모되지만, CPU cache에 비해 상대적으로 연산 시간보다는 I/O 수행 시간이 중요한 DBMS cache에서 적용되어 DBMS의 성능을 개선할 수 있음을 시사한다.
5일 때 가장 인간 기억 인출과정의 많은 현상들에 적합한 결과를 보인다고 언급하였다. 종합해볼 때 d의 값을 0～1사이의 값으로 선택하는 것이 가능하며 이 중 멱함수의 계산 비용이 적은 1을 선택하는 것이 일반적인 환경에서 추천할만하다고 할 수 있다.
λ, d, k를 각각 4e-5, 1, 60으로 고정시키고 cache의 크기에 따른 각 알고리즘의 성능을 측정해보았고 이는 (그림 4)와 같이 나타났다. 캐쉬 크기에 비례하여 모든 알고리즘들이 일정하게 성능이 증가하였으며, 캐쉬 크기에 관계없이 제안하는 ACTR이 타 캐쉬 알고리즘들에 비해 가장 좋은 hit ratio를 보였다. ACTR은 TPC-C 워크로드에 있어 전체 DBMS 크기의 5%～6%에 해당하는 DBMS cache를 사용했을 때, LFRU, LRU, LFU 각각에 대해서 평균적으로 3.

후속연구

이러한 ACT-R과 [5]의 base-level activation은 Belady가 제안한 이상적인 알고리즘에 근접한 성능을 낼 수 있는 휴리스틱 방법을 설계하는데 활용될 수 있다. Belady가 제안한 것처럼 미래에 가장 오랫동안 사용되지 않을 페이지를 교체하는 정책은 현재 다시 인출될 확률이 가장 낮은 페이지를 교체하는 방법으로 근사화(approximation)될 수 있으며, 이는 base-level activation을 캐쉬에 존재하는 각 페이지에 적용하여 계산한 후 이들 중 activation level이 가장 낮은 페이지를 교체하는 것과 동일하다.
향후 연구로서, 보다 많은 인지과학적 아키텍쳐의 특징들을 데이터베이스 기술에 이식하는 연구들을 수행하려고 한다. ACT-R[4]에서 사용하는 지식의 기본 단위인 chunk를 데이터베이스 기술에 적용하여 자주 같이 접근되는 페이지들을 ACT-R의 activation level 이론에 근거하여 chunk로 묶고 prefetching 단위나 페이지 재배치 정책에 chunk 개념을 활용하는 등의 연구가 이루어질 수 있다.

핵심어	질문	논문에서 추출한 답변
	캐쉬란?	자주 접근되는 데이터에 대해서 빠른 접근을 보장하기 위해 사용되는 임시저장소인 캐쉬는 컴퓨터 시스템 내에서 다양한 계층에 존재하며 그 예로는 CPU 캐쉬, Disk 캐쉬, Database Buffer 캐쉬 등이 있다. 하지만 제약된 캐쉬의 저장 공간 내에서 가장 효율적으로 데이터를 관리하기 위해 사용되는 캐쉬 페이지 교체 알고리즘들은 이들 계층에서 모두 공통적으로 사용되고 있다.
	대표적인 캐쉬 페이지 교체 알고리즘은 무엇이 있는가?	대표적인 캐쉬 페이지 교체 알고리즘들로는 LRU[2], LFU[2], LRFU[3] 등이 있다. 이들은 모두 과거의 데이터에 대한 접근 기록에 의존하여 가장 앞으로 사용되지 않을 것 같은 페이지를 교체하는 전략을 취하며, 그러기 위해 과거에 접근된 횟수, 접근된 후로부터 지난 시간 등을 페이지 교체의 기준으로 적용하여 작동한다.
	LRU[2], LFU[2], LRFU[3]의 특징은?	대표적인 캐쉬 페이지 교체 알고리즘들로는 LRU[2], LFU[2], LRFU[3] 등이 있다. 이들은 모두 과거의 데이터에 대한 접근 기록에 의존하여 가장 앞으로 사용되지 않을 것 같은 페이지를 교체하는 전략을 취하며, 그러기 위해 과거에 접근된 횟수, 접근된 후로부터 지난 시간 등을 페이지 교체의 기준으로 적용하여 작동한다. [2]는 이들 대표적인 페이지 교체 알고리즘들 중 과거의 접근된 횟수와 접근된 후로부터 지난 시간을 모두 고려하는 LRFU를 실제 환경에서 가장 효율적인 알고리즘이라고 언급하였다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

인간 기억 인출 과정을 응용하여 설계된 ACT-R 기반 페이지 교체 정책
A novel page replacement policy associated with ACT-R inspired by human memory retrieval process 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

연구과제 타임라인

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

인간 기억 인출 과정을 응용하여 설계된 ACT-R 기반 페이지 교체 정책 A novel page replacement policy associated with ACT-R inspired by human memory retrieval process 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

노홍찬 (6) 박상현 (48)

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

인간 기억 인출 과정을 응용하여 설계된 ACT-R 기반 페이지 교체 정책
A novel page replacement policy associated with ACT-R inspired by human memory retrieval process 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper