KR102316271B1

KR102316271B1 - 데이터 저장장치의 주소 맵핑 테이블 운용 방법

Info

Publication number: KR102316271B1
Application number: KR1020190106688A
Authority: KR
Inventors: 홍유표; 소현주; 송유찬; 천용재; 강협
Original assignee: 동국대학교 산학협력단
Priority date: 2019-08-29
Filing date: 2019-08-29
Publication date: 2021-10-22
Also published as: KR20210027625A

Abstract

본 발명은 데이터 저장장치의 주소 맵핑 테이블 운용 방법에 관한 것으로, (a) 주소 관리 메모리에 주소 맵핑 테이블을 생성하는 단계; (b) 신규 데이터에 관한 쓰기 명령이 있는 경우, 상기 신규 데이터의 논리 주소 값에 제1해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 데이터가 존재하는지 여부를 확인하여 데이터가 존재하지 않는 경우, 상기 해당 세트의 데이터 필드에 상기 데이터의 논리 주소 및 물리 주소를 저장하고 뱅크 접근 순서를 재배열하는 단계; 및 (c) 상기 확인 결과에 따라 상기 세트에 데이터가 기존재하는 경우, 상기 주소 관리 메모리의 해당 주소의 값에 제2해시 함수를 적용하고, 상기 제2해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 데이터의 존부를 확인하여, 데이터가 존재하지 않는 경우 해당 데이터 필드에 상기 신규 데이터의 논리 주소 및 물리 주소를 저장하고 뱅크 접근 순서를 재배열하는 단계;를 포함하여 구성된다.

Description

데이터 저장장치의 주소 맵핑 테이블 운용 방법{METHOD FOR MANAGING OF MEMORY ADDRESS MAPPING TABLE FOR DATA STORAGE DEVICE}

본 발명의 실시예는 데이터 저장장치의 주소 맵핑 테이블 운용 방법에 관한 것으로, SSD의 플래시 메모리 등의 비휘발성 데이터 저장장치에서 주소 맵핑 테이블을 통해서 데이터 저장장치에 저장된 데이터를 찾는 시간적 성능을 향상시키기 위해 뱅크 인터리빙(Bank interleaving)을 최적화한 데이터 저장장치의 주소 맵핑 테이블 운용 방법에 관한 것이다.

비휘발성 데이터 저장장치는 전원이 끊기더라도 저장된 데이터가 소실되지 않는 저장매체를 의미하며, 이에 관한 대표적인 예로서 SSD의 플래시 메모리가 여기에 해당한다.

도 1은 일반적인 플레시 메모리의 구성을 설명하기 위한 도면이다.

플래시 메모리는 기본적으로 다이(Die), 블록(Block), 페이지(Page)로 구성되어 있다. 여기서, Page는 읽기/쓰기 동작의 기본 단위이고, 이러한 Page들이 모여 Block을 구성하며, 또한 Block들이 모여 Die를 구성한다. 이때, 다이(Die)는 단일 실리콘 기판으로 구현이 되는 물리적 단위를 나타낸다.

상술한 바와 같은 비휘발성 데이터 저장장치에 데이터를 저장할 때와 그 저장된 데이터를 검색할 때에는 주소 맵핑 테이블이 활용된다. 여기서, 주소 맵핑 테이블은 CPU 등의 프로세서가 데이터를 요청한 주소인 논리 주소(Logical address)와 실제 해당 저장매체에 데이터가 저장된 물리적 위치를 나타내는 물리 주소(physical address)을 연계하여 등록해둔 관리 테이블을 의미한다. CPU는 논리 주소(Logical address)를 통하여 읽기/쓰기 동작을 요청하게 되며, 주소 맵핑 테이블을 확인하여 물리 주소와 매칭되는 주소로 접근하는 방식에 의한다.

주소 맵핑 테이블은 별도의 메모리(예를 들어, DRAM 등)에 저장된다. DRAM의 저장 공간은 여러 개의 뱅크(Bank)로 이루어져 있다. 뱅크는 행으로 또 나뉘고, 행(row)은 또 열(column)로 또 나뉜다. DRAM에 쓰기 또는 읽기를 할 때 해당하는 뱅크에 행을 찾는 과정이 먼저 이루어지고, 행을 찾은 후에 열에 쓰기 또는 읽기를 시행한다. 행을 찾는 과정에 시간이 소요되고, 열에 쓰기 또는 읽기를 하는 과정에서도 시간이 소요되는데, 이후에 다른 뱅크의 작업을 하려할 때, 현재 뱅크가 쓰기/읽기 작업을 수행하는 다른 뱅크의 행을 미리 활성화 시켜 놓는 것이 가능하다. 그래서 이후에 직전과 같은 뱅크의 다른 행의 메모리에 접근하는 것 보다 더 빠르게 접근이 가능하다. 이를 뱅크 인터리빙(bank interleaving)이라고 한다. 즉, 뱅크 인터리빙이 많이 일어날수록 평균 전송속도가 뱅크 인터리빙이 일어나지 않았을 때보다 빨라지게 된다.

현재의 많은 주소 맵핑 테이블에 관한 알고리즘들이 논리 주소와 물리 주소의 연결을 수행하기 위해 제안되어 왔는데, 이때 연결을 위한 알고리즘들은 통상 해시 함수라는 것을 이용한다.

도 2는 일반적인 해시 함수를 설명하기 위한 도면이고, 도 3은 일반적인 주소 맵핑 테이블을 설명하기 위한 도면이다.

해시 함수(Hash function)란 알고리즘을 수식을 이용하여 표현한 것으로서 입력 값을 연산하여 결과 값인 해시 키(Hash key)출력한다. 해시 키를 통해 주소 맵핑 테이블의 어느 위치에 들어갈 지를 결정하기 때문에 입력 값은 논리 주소가 되고 해쉬 키는 항상 주소 맵핑 테이블의 범위를 벗어나지 않는다. 해시함수로 인한 결과 값은 무작위의 성질을 띠고 있으므로 논리 주소 값이 맵핑주소 테이블 범위 내에서 골고루 분포될 수 있도록 한다.

주소 맵핑 테이블의 위치는 세트(Set)로 표현된다. 세트는 다수의 데이터 필드와 세트 간 맵핑 정보가 담겨있는 세트 맵핑 필드로 구성되어 있다. 하나의 해시 키는 하나의 셋과 일대일 대응이다. 어떤 세트를 사용하는지에 따라 어떤 뱅크에 접근 해야 하는지가 결정된다. 뱅크 인터리빙을 사용할 수 있으면 어떤 뱅크를 사용하는가가 접근 속도에 영향을 미치게 된다.

현재 이용되는 주소 맵핑 테이블은 해시 키에 따른 세트의 뱅크가 하나로 고정 되어 있어서 접근 속도 또한 해시 키에 따라 정해지게 된다.

따라서, 하나의 세트에 여러 개의 뱅크를 할당하여 뱅크 인터리빙 빈도를 높여서 접근 속도를 줄일 수 있는 새로운 주소 관리 알고리즘이 필요하다.

본 발명은 전술한 문제를 해결하기 위해 안출된 것으로서, 본 발명에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법은 데이터 저장장치에 저장된 데이터의 검색 과정에 주소 맵핑 테이블을 활용함에 있어서 논리 주소를 찾는 시간을 줄일 수 있는 주소 맵핑 테이블 운용 방법 및 이에 관한 알고리즘을 제공하기 위한 것이다.

전술한 문제를 해결하기 위한 본 발명의 실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법은 (a) 주소 관리 메모리에 주소 맵핑 테이블을 생성하는 단계; (b) 신규 데이터에 관한 쓰기 명령이 있는 경우, 상기 신규 데이터의 논리 주소 값에 제1해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 데이터가 존재하는지 여부를 확인하여 데이터가 존재하지 않는 경우, 상기 해당 세트의 데이터 필드에 상기 데이터의 논리 주소 및 물리 주소를 저장하고 뱅크 접근 순서를 재배열하는 단계; 및 (c) 상기 확인 결과에 따라 세트에 데이터가 기존재하는 경우, 상기 주소 관리 메모리의 해당 주소의 값에 제2해시 함수를 적용하고, 상기 제2해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 데이터의 존부를 확인하여, 데이터가 존재하지 않는 경우 해당 데이터 필드에 상기 신규 데이터의 논리 주소 및 물리 주소를 저장하고 뱅크 접근 순서를 재배열하는 단계;를 포함한다.

본 발명의 다른 일실시예에 따르면, 상기 제1해시 함수는 사전 지정된 연산을 통해 상기 주소 관리 메모리 내의 주소 값을 배정해주는 함수이고, 상기 제2해시 함수는 상기 주소 관리 메모리 내의 주소 값에 1을 증가시키는 +1 연산 함수일 수 있다.

본 발명의 다른 일실시예에 따르면, 상기 (c) 단계는 상기 제2해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 데이터가 부존재할 때까지, 상기 제2해시 함수의 적용을 반복 수행할 수 있다.

본 발명의 다른 일실시예에 따르면, 상기 주소 맵핑 테이블은 해당 데이터의 논리 주소를 저장하는 1차 테이블(primary table) 및 물리 주소를 저장하는 2차 테이블(secondary table)을 포함할 수 있다.

본 발명의 다른 일실시예에 따르면, 상기 뱅크의 접근 순서는 뱅크 인터리빙의 효과를 얻기 위해 접근한지 가장 오래된 순서로 결정할 수 있다.

본 발명의 다른 일실시예에 따르면, 상기 1차 테이블은 상기 제1해시 함수 만을 적용하여 상기 주소 맵핑 테이블에 논리 주소 및 물리 주소가 맵핑 저장된 케이스와, 상기 제2해시 함수를 적용하여 상기 주소 맵핑 테이블에 논리 주소 및 물리 주소가 맵핑 저장된 케이스를 구분하고, 상기 1차 테이블에서 세트의 모든 데이터 필드에 데이터가 기존재하는 경우에 상기 제2 해시 함수를 적용하여 대응되는 다음 세트의 위치정보(next set id(nsid))를 세트 맵핑 필드에 입력할 수 있다.

본 발명의 다른 일실시예에 따르면, (d) 데이터에 관한 읽기 명령이 있는 경우, 읽기 명령된 데이터의 논리 주소 값에 상기 제1해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 읽기 명령 된 데이터의 논리 주소가 존재하는지를 확인하는 단계; 및 (e) 상기 확인 결과, 상기 읽기 명령된 데이터의 논리 주소가 존재하는 경우, 해당 데이터 필드의 물리 주소를 불러오는 단계;를 더 포함할 수 있다.

본 발명의 다른 일실시예에 따르면, (f) 상기 읽기 명령된 논리 주소의 데이터가 1차 테이블의 세트에 존재하지 않는 경우, 세트 내의 세트 맵핑 필드의 nsid가 존재할 때까지 다음 세트를 확인하여, 상기 다음 세트의 위치 정보(nsid)에 의해서 동일한 논리 주소가 입력된 주소 관리 메모리 내의 데이터 필드가 존재하는 경우 해당 주소의 논리 주소의 물리 주소를 읽어 들이는 단계;를 더 포함할 수 있다.

본 발명의 다른 일실시예에 따르면, 상기 (f) 단계는 다음 세트의 위치 정보를 찾기 위한 과정으로서 수행되는 세트 맵핑 필드의 nsid 검색이, 세트 맵핑 필드에 nsid가 존재하지 않을 때까지 수행될 수 있다.

또한, 본 발명의 일실시예에 따른 컴퓨터로 읽을 수 있는 기록 매체는 상기 데이터 저장장치의 주소 맵핑 테이블 운용 방법이 기록된다.

본 발명의 실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법은 데이터 저장장치에 저장된 데이터의 검색 과정에 주소 맵핑 테이블을 활용함에 있어서 논리 주소를 찾는 시간을 줄일 수 있고, 이에 따라 데이터 검색 시간을 최소화하여 처리할 수 있는 효과가 있다.

도 1은 일반적인 플레시 메모리의 구성을 설명하기 위한 도면이다.
도 2는 일반적인 해시 함수를 설명하기 위한 도면이다.
도 3은 일반적인 주소 맵핑 테이블을 설명하기 위한 도면이다.
도 4는 본 발명의 일실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법으로서 쓰기 명령 시의 동작 흐름을 설명하기 위한 도면이다.
도 5 내지 도 14는 본 발명의 일실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법으로서 쓰기 명령 시의 동작 방법을 설명하기 위한 도면이다.
도 15는 본 발명의 일실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법으로서 읽기 명령 시의 동작 흐름을 설명하기 위한 도면이다.
도 16은 본 발명의 일실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법으로서 읽기 명령 시의 동작을 설명하기 위한 도면이다.

본 발명은 다양한 변환을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 특정 실시예들을 도면에 예시하고 상세한 설명에 상세하게 설명하고자 한다. 그러나, 이는 본 발명을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변환, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다.

본 발명을 설명함에 있어서, 관련된 공지 기술에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우 그 상세한 설명을 생략한다.

도 4는 본 발명의 일실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법으로서 쓰기 명령 시의 동작 흐름을 설명하기 위한 도면이고, 도 5 내지 도 14는 본 발명의 일실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법으로서 쓰기 명령 시의 동작 방법을 설명하기 위한 도면이다.

이후부터는 도 4 내지 도 14를 참조하여 본 발명의 일실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법을 설명하기로 한다.

도 4를 참조하면, 본 발명의 일실시예에 따른 주소 맵핑 테이블 운용 방법은, 신규 데이터에 관한 쓰기 명령이 있는 경우, 상기 신규 데이터의 논리 주소 값에 제1해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 데이터가 존재하는지 여부를 확인하고, 데이터가 부존재하는 경우 상기 해당 주소의 세트에 상기 신규 데이터의 논리 주소 및 물리 주소를 저장한다.

반대로, 상기 확인 결과에 따라 데이터가 기존재하는 경우 상기 주소 관리 메모리의 해당 주소의 값에 제2해시 함수를 적용하되, 상기 제2해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 신규 데이터의 입력 가능 여부를 확인하여, 신규 데이터가 입력 가능한 경우 상기 신규 데이터의 논리 주소 및 물리 주소를 저장한다.

이때, 상기 제2해시 함수의 적용은, 상기 제2해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 신규 데이터의 입력 가능한 데이터 필드가 나올 때까지 반복 수행될 수 있다.

보다 구체적으로, 데이터에 관한 쓰기 명령이 있는 경우, 논리 주소값에 제1해시 함수를 적용한 해시 키에 대응되는 세트 내 데이터 필드에 동일 논리 주소 및 신규 데이터 입력 가능 여부를 확인하고(S410), 동일 논리 주소가 존재하지 않으며(S420), 신규 데이터의 입력이 가능한 경우(S430), 동일 논리 주소 및 신규 데이터 입력이 가능한 세트가 나올 때까지 nsid를 이용해 세트 내의 데이터를 확인하여, nsid가 존재하지 않을 경우, 해당 주소에 제2해시 함수를 적용해 세트를 확인하여(S440), 해당 주소의 데이터 필드에 논리 주소와 물리 주소를 기록할 수 있다(S450).

CPU에서 논리주소(Logical address) 100이라는 데이터 쓰기의 명령이 들어왔을 때의 예시를 통하여 동작에 대한 설명을 하기로 한다. 예시에서의 논리주소 100에 대한 제 1 해시 함수의 해시 키는 2로 설정 하였고, 뱅크 접근 순서의 초기값은 임의로 0번, 3번, 1번, 2번, 뱅크로 지정해주었다. 그리고, 설명의 편의를 위해 주소 맵핑 테이블이 저장되는 주소 관리 메모리는 DRAM인 것으로 가정하고, 세트 내의 필드의 개수는 각 뱅크 별 2개씩 0번 뱅크에 세트 맵핑 정보가 포함된 세트 맵핑 필드와 데이터 필드가 배정되고, 1, 2, 3 번 뱅크에 각각 2개의 데이터 필드가 배정 되어서 총 8개의 필드를 가진다.

뱅크의 접근 순서는 뱅크 인터리빙의 효과를 얻기 위해 가장 오래된 순서로 접근한다. 따라서, 현재 접근할 뱅크는 가장 오래 전에 접근하였던 t-4의0번 뱅크이고, 다음으로 t-3의 3번 뱅크, t-2의 1번 뱅크, t-2의 2번 뱅크이다.

도 5를 참조하면, 현재 뱅크에 접근하는 시점을 t라고 했을 때 t-n은 그보다 n번 전에 접근하였던 뱅크임을 나타낸다. 따라서 현재 접근할 뱅크는 t-4의 뱅크이고, 이 뱅크는 접근한 이후에 가장 최근에 접근한 뱅크(t-1)로 변경된다. 따라서 다음 접근 순서를 위해 t-4에 있었던 뱅크가 t-1로 이동하고 나머지 t-n에 담겨 있던 뱅크는 t-(n+1)으로 이동하게 된다.

쓰기나 읽기동작으로 인해 현재 사용한 뱅크가 이전의 t-4에 있던 뱅크가 아닐 상황이 존재한다. 예를 들면 기존의 뱅크 순서가 0번 1번 2번 3번 이었는데, 같은 논리주소가 2번 뱅크에 존재한다면 가장 최근에 접근한 뱅크(t-1)가 2번 뱅크로 변경되어 다음 동작으로 넘어가게 된다. 이에 따라 접근 순서 패턴의 변동이 일어날 수 있다. 이 경우에는 현재 사용한 뱅크를 기준으로 뱅크 접근 순서를 변경하여 준다. 예를 들어 t-2에 있던 뱅크를 현재 사용하게 될 경우에는 t-2가 가장 최근에 사용한 뱅크가 되므로 t-1에 들어가게 되고 t-2에 는 t-1에 있던 뱅크가 들어가게 된다.

도 6 및 도 7을 참조하면, 현재 접근할 뱅크는 가장 오래 전에 접근하였던 t-4의0번 뱅크이고, 다음으로 t-3의 3번 뱅크, t-2의 1번 뱅크, t-2의 2번 뱅크이다.

[쓰기 동작 시 1차 테이블의 셋에 비어있는 공간이 존재하는 경우]

논리 주소 100이 제 1 해시 함수 연산에 의해 해시 키는 2의 값을 갖게 된다. 오래 전에 사용한 뱅크의 순서가 0번, 3번, 1번, 2번이라는 것을 확인한다. 0번 뱅크부터 오래 전에 사용된 뱅크 순으로 해시 키 3번 셋의 각 뱅크 별 첫번째 데이터 필드와 세트 맵핑 필드를 읽고, 같은 순으로 해시 키3번의 셋의 각 뱅크 별 두번째 데이터 필드를 읽어서 7개의 데이터 필드 중 같은 논리 주소 또는 비어있는 공간의 존부 여부를 파악한다.

같은 논리 주소가 없고, 비어 있는 공간이 있음을 확인하였으므로 비어있는 데이터 필드들 중 가장 처음 찾은 비어있는 데이트 필드인 1번 뱅크의 첫번째 데이터 필드에 논리 주소와 물리 주소를 저장한다. 이 경우 접근할 뱅크 순서 패턴이 바뀌게 되므로, 도 8과 같이 순서가 바뀌게 된다. 1번 뱅크가 가장 최근에 사용되었으므로 t-1이 된 것을 확인할 수 있다.

[쓰기 동작 시 1차 테이블의 셋의 비어있는 공간이 존재하지 않고 nsid가 비어있는 경우]

논리 주소 100이 제 1 해시 함수 연산에 의해 해시 키는 2의 값을 갖게 된다. 오래 전에 사용한 뱅크의 순서가 0번, 3번, 2번, 1번 뱅크라는 것을 확인한다. 0번 뱅크부터 오래 전에 사용된 뱅크 순으로 3번 셋의 뱅크 별 첫번째 데이터 필드와 세트 맵핑 필드를 읽고, 같은 순으로 3번 셋의 뱅크 별 두번째 데이터 필드를 7개의 데이터 필드 중 같은 논리 주소 또는 비어있는 공간의 존부 여부를 파악한다. 파악한 결과 같은 논리 주소가 없고 3번 셋의 모든 공간이 차 있으므로 세트 맵핑 필드에 nsid의 존부 여부를 확인하고, 이때 비어 있으므로 제2 해시 함수를 통하여2차 테이블의 set0이 배정되고, 2차 테이블의 set0의 위치정보가 1차 테이블의 3번 세트의 세트 맵핑 필드의 nsid에 입력된다. 그 다음으로 2차 테이블로 넘어가서 nsid에 맞는 셋을 다시 오래 전에 사용한 뱅크의 순서대로 읽는다. 같은 논리 주소가 없고, 비어있는 공간이 있음을 확인하였으므로 3번 뱅크의 첫번째 데이터 필드에 논리 주소와 물리 주소를 저장한다. 이 경우에는 1차 테이블의 가장 최근에 사용한 뱅크가 0번 뱅크가 되므로, 도 10과 같이 뱅크 접근 순서가 바뀌게 된다.

[쓰기 동작 시 1차 테이블의 셋의 비어있는 공간이 존재하지 않고 nsid가 차있는 경우]

논리 주소 100이 제1 해시 함수 연산에 의해 해시 키는 2의 값을 갖게 된다. 오래 전에 사용한 뱅크의 순서가 0번, 3번, 1번, 2번 뱅크라는 것을 확인한다. 0번 뱅크부터 오래 전에 사용된 뱅크 순으로 3번 셋의 뱅크 별 첫번째 데이터 필드와 세트 맵핑 필드를 읽고, 같은 순으로 3번 셋의 뱅크 별 두번째 데이터 필드를 읽어서 7개의 데이터 필드 중 같은 논리 주소 또는 비어있는 데이터 필드의 존부 여부를 파악한다. 파악한 결과 같은 논리 주소가 없고 3번 셋의 모든 데이터 필드가 차 있으므로 세트 맵핑 필드의 nsid의 존부 여부를 확인하고 nsid가 있으면 nsid에 기재되어 있는 해시 키를 읽어 제 2 속성 필드에서 대응되는 셋을 다시 오래 전에 사용한 뱅크의 순서대로 읽는다. 확인 결과 같은 논리 주소가 없고, 비어있는 데이터 필드가 있음을 확인하였으므로 3번 뱅크 첫번째 데이터 필드에 논리 주소와 물리 주소를 저장한다. 이 경우에는 0번 뱅크의 세트 맵핑 필드를 사용해야 하지 않으므로 뱅크 접근순서에 변동이 없다.

[쓰기 동작 시 이전에 1차 테이블에 썼던 논리 주소에 다시 쓰는 경우]

논리 주소 100이 제 1 해시 함수 연산에 의해 해시 키는 2의 값을 갖게 된다. 뱅크 접근 순서를 확인한 결과 오래 전에 사용한 뱅크의 순서가 0번, 3번, 2번, 1번 뱅크 라는 것을 확인 하였다. 따라서 0번 뱅크부터 오래 전에 사용된 뱅크 순으로 3번 셋의 뱅크 별 첫번째 데이터 필드와 세트 맵핑 필드를 읽고, 같은 순으로 3번 셋의 뱅크 별 두번째 데이터 필드를 읽어서 7개의 데이터 필드 중 같은 논리 주소와 비어있는 공간의 존부 여부를 파악한다. 1번 뱅크 첫번째 데이터 필드에 같은 논리 주소가 존재함을 확인하였으므로 그 데이터 필드에 새로운 물리주소를 덮어쓴다. 이 경우에는 마지막으로 사용하는 뱅크가 바뀔 수 있어 이전에 사용한 뱅크의 순서가 변경되는게 일반적이지만 뱅크의 순서가 원래0번, 3번, 2번, 1번으로 1번 뱅크가 t-1 에 존재하므로 갱신하여 줄 필요가 없다.

도 15는 본 발명의 일실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법으로서 읽기 명령 시의 동작 흐름을 설명하기 위한 도면이며, 도 16은 본 발명의 일실시예에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법으로서 읽기 명령 시의 동작을 설명하기 위한 도면이다.

도 15를 참조하면, 본 발명의 실시예에 따른 주소 맵핑 테이블 운용 방법은, 데이터에 관한 읽기 명령이 있는 경우, 읽기 명령 된 데이터의 논리 주소 값에 상기 제1해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 읽기 명령 된 데이터의 논리 주소가 존재하는지를 확인한다. 상기 확인 결과, 상기 읽기 명령 된 데이터의 논리 주소가 존재하는 경우, 해당 논리 주소와 대응되는 물리 주소로부터 데이터를 읽어 들인다

반면, 상기 확인 결과, 상기 읽기 명령된 데이터의 논리 주소가 존재하지 않는 경우, 상기 주소 관리 메모리 내의 주소를 검색될 때까지 세트 맵핑 필드의nsid를 통해 맵핑된 2차 테이블의 세트에 읽기 명령 된 데이터의 논리 주소가 존재하는지를 확인한다. 상기 확인 결과, 상기 읽기 명령 된 데이터의 논리 주소가 존재하는 경우, 해당 논리 주소와 대응되는 물리 주소를 읽어 들인다. 이때, 읽기 명령 된 논리 주소가 입력된 세트를 찾기 위한 과정으로서 수행되는 상기 세트 맵핑 필드의 nsid를 통해 다음 세트 검색은, 상기 세트 맵핑 필드의 nsid가 존재하지 않을 때까지를 검색 종점으로 하여 수행될 수 있다.

예를 들어, 데이터에 관한 읽기 명령이 있는 경우, 논리 주소값에 제1해시 함수를 적용한 해시 키에 대응되는 세트 내 동일 논리 주소를 확인하고(S510), 동일 논리 주소가 존재하지 않으면(S520), 동일 논리 주소가 있는 세트가 나올 때까지 nsid(다음 세트 맵핑정보)를 이용해 세트를 확인하고(S530), 해당 주소의 데이터 필드의 물리 주소를 읽어 들일 수 있다(S540).

이후, 뱅크 접근 순서의 초기값은 임의로 0번, 3번, 2번, 1번 뱅크로 지정해주었을 때, CPU에서 논리 주소(Logical address) 100이라는 데이터 읽기의 명령이 들어왔을 때의 예시를 통하여 동작에 대한 설명을 하기로 한다. 예시에서의 논리주소 100에 대한 제 1 해시 함수의 해시 키는 2로 설정 하였고, 뱅크 접근 순서의 초기값은 임의로 0번, 3번, 1번, 2번 뱅크로 지정해주었다.

[1차 테이블의 셋에 같은 논리 주소가 존재하는 경우]

논리 주소 100이 제 1 해시 함수 연산에 의해 해시 키는 2의 값을 갖게 된다. 오래 전에 사용한 뱅크의 순서가 도 13의 0번, 3번, 2번, 1번 뱅크라는 것을 확인한다. 이 순서대로 2번 셋의 뱅크 별 첫번째 데이터 필드와 세트 맵핑 필드 확인한다. 1번 뱅크의 첫번째 데이터 필드에 동일한 논리 주소가 있음을 확인 하였으므로 이 데이터 필드에 저장되어 있는 물리 주소를 읽어온다. 마지막으로 사용한 뱅크가 1번 뱅크 이기 때문에 뱅크의 접근 순서는 바뀌지 않아도 된다.

[1차 테이블의 셋에 같은 논리 주소가 존재하지 않고, nsid가 존재하지 않는 경우]

논리 주소 100이 제 1 해시 함수 연산에 의해 해시 키는 2의 값을 갖게 된다. 오래 전에 사용한 뱅크의 순서가 0번, 3번, 2번, 1번 뱅크라는 것을 확인한다. 이 순서대로 3번 셋의 뱅크 별 첫번째 데이터 필드와 세트 맵핑 필드 확인한다. 확인 결과 데이터 필드에서 같은 논리 주소를 찾지 못하였으므로 이어서 각 뱅크의 두번째 데이터 필드를 확인한다. 그럼에도 불구하고 같은 논리 주소를 찾지 못하였고, nsid 또한 존재하지 않기 때문에 이 논리 주소에 대한 읽기 동작을 중단하고 다음 동작을 시작한다. 이 경우는 뱅크를 8번씩 모두 동등하게 사용하기 때문에 뱅크의 접근 순서가 바뀌지 않는다.

[1차 테이블의 셋에 같은 논리 주소가 존재하지 않고, nsid에 대응되는 해시 키의 셋에 같은 논리 주소가 존재하는 경우]

논리 주소 100이 제 1 해시 함수 연산에 의해 해시 키는 2의 값을 갖게 된다. 오래 전에 사용한 뱅크의 순서가 0번, 3번, 2번, 1번 뱅크라는 것을 확인한다. 이 순서대로 3번 셋의 각 뱅크별 첫번째 데이터 필드에 같은 논리 주소가 있는지를 확인한다. 같은 논리 주소를 찾지 못하였으므로 이어서 각 뱅크 별 두번째 데이터 필드를 확인한다. 같은 논리 주소를 찾지 못하였으므로, 세트 맵핑 필드의 nsid에 기재되어 있는 해시 키를 읽어 2차 테이블에서 대응되는 세트를 다시 오래 전에 사용한 뱅크의 순서대로 읽는다. 2번 뱅크의 첫번째 데이터 필드에 같은 논리 주소가 있음을 확인 하였으므로 이 곳에 저장되어 있는 물리 주소를 읽어온다.

상술한 본 발명에 따른 데이터 저장장치의 주소 맵핑 테이블 운용 방법 은 컴퓨터로 읽을 수 있는 기록 매체에 컴퓨터가 읽을 수 있는 코드로서 구현되는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록매체로는 컴퓨터 시스템에 의하여 해독될 수 있는 데이터가 저장된 모든 종류의 기록 매체를 포함한다. 예를 들어, ROM(Read Only Memory), RAM(Random Access Memory), 자기 테이프, 자기 디스크, 플래쉬 메모리, 광 데이터 저장장치 등이 있을 수 있다. 또한, 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 통신망으로 연결된 컴퓨터 시스템에 분산되어, 분산방식으로 읽을 수 있는 코드로서 저장되고 실행될 수 있다.

전술한 바와 같은 본 발명의 상세한 설명에서는 구체적인 실시예에 관해 설명하였다. 그러나 본 발명의 범주에서 벗어나지 않는 한도 내에서는 여러 가지 변형이 가능하다. 본 발명의 기술적 사상은 본 발명의 전술한 실시예에 국한되어 정해져서는 안 되며, 특허청구범위뿐만 아니라 이 특허청구범위와 균등한 것들에 의해 정해져야 한다.

Claims

데이터 저장장치의 주소 맵핑 테이블 운용 방법에 있어서,
(a) 주소 관리 메모리에 주소 맵핑 테이블을 생성하는 단계;
(b) 신규 데이터에 관한 쓰기 명령이 있는 경우, 상기 신규 데이터의 논리 주소 값에 제1해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 데이터가 존재하는지 여부를 확인하여 데이터가 존재하지 않는 경우, 상기 해당 세트의 데이터 필드에 상기 데이터의 논리 주소 및 물리 주소를 저장하고 뱅크 접근 순서를 재배열하는 단계; 및
(c) 상기 확인 결과에 따라 상기 세트에 데이터가 기존재하는 경우, 상기 주소 관리 메모리의 해당 주소의 값에 제2해시 함수를 적용하고, 상기 제2해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 데이터의 존부를 확인하여, 데이터가 존재하지 않는 경우 해당 데이터 필드에 상기 신규 데이터의 논리 주소 및 물리 주소를 저장하고 뱅크 접근 순서를 재배열하는 단계;
를 포함하는 데이터 저장장치의 주소 맵핑 테이블 운용 방법.
청구항 1에 있어서,
상기 제1해시 함수는,
사전 지정된 연산을 통해 상기 주소 관리 메모리 내의 주소 값을 배정해주는 함수이고,
상기 제2해시 함수는,
상기 주소 관리 메모리 내의 주소 값에 1을 증가시키는 +1 연산 함수인 데이터 저장장치의 주소 맵핑 테이블 운용 방법.
청구항 1에 있어서,
상기 (c) 단계는,
상기 제2해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 데이터가 부존재할 때까지, 상기 제2해시 함수의 적용을 반복 수행하는 데이터 저장장치의 주소 맵핑 테이블 운용 방법.
청구항 1에 있어서,
상기 주소 맵핑 테이블은,
해당 데이터의 논리 주소를 저장하는 1차 테이블(primary table) 및 물리 주소를 저장하는 2차 테이블(secondary table)을 포함하는 데이터 저장장치의 주소 맵핑 테이블 운용 방법.
청구항 1에 있어서,
상기 뱅크의 접근 순서는,
뱅크 인터리빙의 효과를 얻기 위해 접근한지 가장 오래된 순서로 결정하는 데이터 저장장치의 주소 맵핑 테이블 운용 방법.
청구항 4에 있어서,
상기 1차 테이블은,
상기 제1해시 함수 만을 적용하여 상기 주소 맵핑 테이블에 논리 주소 및 물리 주소가 맵핑 저장된 케이스와, 상기 제2해시 함수를 적용하여 상기 주소 맵핑 테이블에 논리 주소 및 물리 주소가 맵핑 저장된 케이스를 구분하고, 상기 1차 테이블에서 세트의 모든 데이터 필드에 데이터가 기존재하는 경우에 상기 제2 해시 함수를 적용하여 대응되는 다음 세트의 위치정보(next set id(nsid))를 세트 맵핑 필드에 입력하는 데이터 저장장치의 주소 맵핑 테이블 운용 방법.
청구항 1에 있어서,
(d) 데이터에 관한 읽기 명령이 있는 경우, 읽기 명령된 데이터의 논리 주소 값에 상기 제1해시 함수를 적용한 결과값에 상응하는 상기 주소 관리 메모리 내의 해당 세트의 데이터 필드에 읽기 명령 된 데이터의 논리 주소가 존재하는지를 확인하는 단계; 및
(e) 상기 확인 결과, 상기 읽기 명령된 데이터의 논리 주소가 존재하는 경우, 해당 데이터 필드의 물리 주소를 불러오는 단계;
를 더 포함하는 데이터 저장장치의 주소 맵핑 테이블 운용 방법.
청구항 7에 있어서,
(f) 상기 읽기 명령된 논리 주소의 데이터가 1차 테이블의 세트에 존재하지 않는 경우, 세트 내의 세트 맵핑 필드의 nsid가 존재할 때까지 다음 세트를 확인하여, 상기 다음 세트의 위치 정보(nsid)에 의해서 동일한 논리 주소가 입력된 주소 관리 메모리 내의 데이터 필드가 존재하는 경우 해당 주소의 논리 주소의 물리 주소를 읽어 들이는 단계;
를 더 포함하는 데이터 저장장치의 주소 맵핑 테이블 운용 방법.
청구항 8에 있어서,
상기 (f) 단계는,
다음 세트의 위치 정보를 찾기 위한 과정으로서 수행되는 세트 맵핑 필드의 nsid 검색이, 세트 맵핑 필드에 nsid가 존재하지 않을 때까지 수행되는 데이터 저장장치의 주소 맵핑 테이블 운용 방법.
컴퓨터에 의해 수행될 때, 청구항 1 내지 청구항 9 중 어느 한 항에 의한 데이터 저장장치의 주소 맵핑 테이블 운용 방법을 수행하는 프로그램이 기록된 컴퓨터로 읽을 수 있는 기록 매체.