선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 이러한 연산들에 소요되는 시간이 트리 검색을 효율적으로 수행함으로써 얻을 수 있는 성능 개선 효과보다 크게 되면 전체적인 프로그램의 성능을 저하시킬 수 있다. 따라서 본 논문은 트리의 생성이나 수정보다 검색 연산이 빈번한 경우에 초점을 둔다.
- 하지만 FPGA를 사용하는 방법은 추가적인 하드웨어를 필요로 하므로 트리 검색의 성능을 개선하고자 할 경우 검색할 데이터의 지역성을 향상 시키는 것이 한 방법이 될 수 있다. 본 논문에서는 트리를 DFS(Depth First Search)로 검색할 경우 데이터 지역성을 향상 시킬 수 있는 배열 기반 트리의 구조와 생성 방법에 대하여 기술한다. 본 논문의 구성은 다음과 같다.
- 본 단락에서는 연결 리스트 트리를 배열 트리로 바꾸는데 필요한 데이터 타입의 변경에 대하여 서술하고, 변경된 데이터 타입에 저장 될 내용들을 계산하면서 연결 리스트 트리를 배열 트리로 변환하는 방법을 설명한다.
- 트리 구조의 생성이나 수정이 적고 한번 구성한 데이터를 반복적으로 검색하는 경우라면 트리 생성이나 수정 시간이 조금 증가하더라도 효율적으로 검색할 수 있는 데이터의 구조를 작성하는 것이 바람직하다. 본 연구에서는 데이터 지역성을 저해하는 연결 리스트 트리를 배열 트리로 변환함으로써 데이터의 지역성을 충분히 활용할 수 있도록 하였다. 배열 트리 상에서 작은 크기의 데이터베이스를 검색할 경우에 BFS와 DFS검색 모두 성능상의 차이가 크지 않지만, 데이터의 크기가 커짐에 따라 2배에서 4배까지의 성능개선 효과를 보였다.
가설 설정
- 트리의 루트 노드는 배열의 첫 번째 노드에 저장되고 인덱스는 0이다. 임의의 A 노드가 B 노드의 루트 노드이고 배열 상에서 두 노드가 10개의 노드만큼 떨어져 있다고 가정하자. 이때 상대적 주소를 사용하면 A는 B를 가리키는 인덱스로 10을 저장한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.