DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

설아 채
5 years ago
Views:

1 우선순위큐를이용한 A* 기반최단경로탐색기법 안진호 *, 박민지 *, 강성호 **, 문병인 *** Shortest Path Search Method using A* Algorithm with Priority Queue Jin-Ho Ahn*, Min-Ji Park*, Sungho Kang**, and Byungin Moon*** 본논문은지식경제부산업기술개발사업으로지원된연구임 ( 과제번호 : ) 요약 본논문에서는최단경로를고속으로탐색하기위한 A* 알고리즘및관련하드웨어구조를제안한다. 제안된구조는기존 A* 기반경로탐색에서가장오랜시간이걸리는오픈리스트구조를우선순위큐로구현하여노드정보탐색과정보처리기능을분산처리할수있으며상기구조에적합한알고리즘을통하여하드웨어오버헤드를줄이면서도경로탐색에필요한시간을크게단축시킬수있다. 시뮬레이션결과기존 A* 와동일한성능을유지하면서하드웨어구현을위한병렬처리구조에적합함을확인할수있었다. Abstract In this paper, we propose the hardware architecture based on A* algorithm finding the shortest path in high-speed and the algorithm suitable for it. The proposed hardware architecture uses a priority queue for Open list generally consuming the longest time within A*-based path search, thus it can separate the search for node information from the data processing of node information. Finally, the algorithm developed for proposed architecture realizes the reduced the shortest path search time with affordable hardware costs. Simulation results show the proposed architecture and its related algorithm are fit for hardware implementation for their performance and parallel processing capability. Key words shortest path search, A* algorithm, priority queue Ⅰ. 서론 네비게이션의경로안내서비스는운전자가출발 지와목적지를입력하면양노드간의평균소요시간이나거리등을고려하여최적경로정보를제공하는것이다. 최적경로탐색을위하여먼저출발지 * 호서대학교전자공학과 ** 연세대학교전기전자공학과 *** 경북대학교전자공학부 제 1 저자 (First Author): 안진호, 교신저자 (Corresponding Author): 문병인 접수일 : 2010 년 07 월 21 일, 수정일 : 1 차 년 08 월 04 일, 게재확정일 : 2010 년 08 월 07 일

2 2 韓國情報技術學會論文誌제 8 권제 8 호 2010 년 08 월 와목적지, 그리고탐색하고자하는경로를출발지, 목적지, 그리고두지점사이에위치한경유지로표현하고이를점으로표현한다. 그리고두점사이의선으로양지점이서로연결되어있음을나타낸다. 상기와같이탐색경로를점과선으로구성된 2차원그래프로표현하고각선에서는연결된두지점사이를이동하는데필요한비용, 예를들어이동시간이나거리등을나타내게한다. 결국최적거리탐색문제는출발지에서경유지를거쳐목적지에이르기까지지나간경로의목표비용을최소화시키는문제로정리된다. 현재제안되었거나사용되는최단경로탐색알고리즘들은그수와종류가무척다양하고도로의구성이나간선의수에따라그적용결과또한일정치않으나다익스트라알고리즘, 양방향다익스트라알고리즘, ALT(A* search, Landmarks and the Triangle inequality) 알고리즘등이주로적용되고있다고알려져있다 [1]. 그러나최근의경로탐색알고리즘은최적경로에대한정보로서거리와평균소요시간, 도로정보 ( 국도와고속도로 ) 등을채택하고있으며기본적으로사용자선택에따라 2-3개의추천경로를제공하고있다 [2]. 따라서여러최적경로비용선정의기준, 즉최단시간 / 거리 / 혹은도로정보등을복합적으로고려해야하지만현존네비게이션시스템은경로탐색을소프트웨어기반으로구현하고있으므로유연한기능수행을위해서는높은사양의내장프로세서가필요하다. 또한저급프로세서를탑재한휴대용기기의경우너무복잡한알고리즘이나메모리리소스를요구하는네비게이션프로그램의실제적용이어려울것이다. 이에 FPGA나전용하드웨어기반의경로탐색기연구가광범위하게이루어지고있으며 [3]-[4] 본논문에서는경로탐색알고리즘으로가장널리활용되는 A* 알고리즘을고속으로동작시킬수있는방법과관련구조를제안한다. A* 알고리즘의노드목록으로는 Open list 와 Closed list 가있다. Open list는조사하지않은노드들이담겨있으며, Closed list는이미조사한노드들이담겨져있다. 초기노드목록에는탐색된곳이없으므로 Closed list는비어있고 Open list는처음위치, 즉시작노드만갖고있다. 이후탐색과정에서 Open list에있는가장낮은비용의노드를가져와다음노드로지정하고, 해당노드는 Open list에서 Closed list로이동된다. 상기노드가목표노드가아니면인접한노드들을정렬해서아직탐색되지않은곳이라면 Open list에넣고, 이미 Open list에있는것일때는그노드를통하는새로운경로가이전보다비용이싸면그노드의정보를업데이트한다. 상기동작을목표노드에도달할때까지반복적으로수행하게된다. A* 에서사용되는비용계산수식은식 (1) 과같다. F = G + H (1) 식 (1) 에서 F는전체비용을나타내며, G는시작노드부터현재노드까지의누적된비용을나타낸다. 그리고 H는휴리스틱값으로현재노드에서목표노드까지의추정비용을나타내며, 일반적으로목표노드까지의일직선거리값이사용된다. Ⅱ. A* 알고리즘 A* 는검색공간의특정노드에이웃한노드들을조사해나가면서시작노드로부터목표노드로이르는가장싼비용의경로를찾는알고리즘이다. 그림 1. A* 알고리즘의유사코드 Fig. 1. Pseudocode of A* algorithm

A* 기반최단경로탐색하드웨어의전체블럭도 Fig. 2. Block diagram of A*-based shortest path search engine 그림 2에서제안하는고속최단경로탐색하드웨어의전체블럭도를개괄적으로나타내었다. 하드웨어는크게 4개의모듈로구성되어있으며각모듈에대한설명은다음과같다.

3 우선순위큐를이용한 A* 기반최단경로탐색기법 3 A* 알고리즘의유사코드를그림 1에서나타내었다 [5]. Ⅲ. A* 기반고속최단경로탐색기법 3.1 하드웨어구조 Node_ID는노드별 identifier이며 parent는현 Node_ID의상위 Node_ID를의미한다. Status는현재저장된노드정보의유효성여부를가리키며 capacity는현재노드의하위노드중빈공간수를표시한다. 괄호안은각데이터의크기이며 max(f) 는 F의최대값을가리킨다. 그림 3. 각우선순위큐의데이터형태 Fig. 3. Data format of a priority queue 그림 2. A* 기반최단경로탐색하드웨어의전체블럭도 Fig. 2. Block diagram of A*-based shortest path search engine 그림 2에서제안하는고속최단경로탐색하드웨어의전체블럭도를개괄적으로나타내었다. 하드웨어는크게 4개의모듈로구성되어있으며각모듈에대한설명은다음과같다. Link DB: Node사이의링크정보 Node DB: Node 정보 ( 특히위 / 경도좌표 ) Path Finder: A* main controller Priority Queue Manger: 우선순위큐및관련제어기 Closed List: 한번거쳐간노드들의집합 링크와노드 DB, 그리고 Closed list는기존 A* 에서사용되는정보들의보관장소이고경로탐색기는하드웨어의최상위제어기이다. 결국상기하드웨어의핵심은우선순위큐매니저이며당모듈은 A* 알고리즘중 Open list에해당하는 Npq개 (2의지수배로설정 ) 의우선순위큐와 4개의레지스터, 그리고우선순위큐제어기로구성된다. (2) 우선순위큐의데이터저장구조제안된구조에서사용된우선순위큐는다음노드를선택하기위한후보노드들을저장하고있는히프형태의공간이다 [6]-[7]. 간단한예를통하여큐의데이터저장구조를설명하도록하겠다. 그림 4는총 15개의노드정보를저장할수있는 4단계우선순위큐이다. 원안의숫자는저장된노드정보중 F값을가리키며빨간색숫자는 Node_ID를의미한다. 큐는히프형태로표현되며하나의 parent 노드 i는좌측 child 노드 2i와우측 child 2i+1로연결된다 ( 여기서 i는 Node_ID임 ). Node_ID를메모리주소로가정할때큐는메모리상에그림 4 테이블과같이저장되며 status 중 A는저장된값이유효한 active queue 상태이고 I는반대로 inactive를나타낸다. 3.2 우선순위큐매니저 (1) 우선순위큐의데이터형태 각큐에저장되는데이터형태는그림 3 과같다. 그림 4. 우선순위큐의데이터저장구조예 Fig. 4. Example of data structure in the priority queue

4 4 韓國情報技術學會論文誌제 8 권제 8 호 2010 년 08 월 그림 4의예는 F값이작은순서대로상위레벨에저장되는최소값우선형태이며다음과같은특성을갖는다 ( 단 pq[j] 는 pq[i] 의 child 노드이다 )[7]. pq[i] 와 pq[j] 가모든 active 상태이면 pq[i] 의 F값은 pq[j] 보다작거나같다. pq[j] 가 active 상태이면 pq[i] 도반드시 active 상태여야한다. pq[i] 의 capacity는 pq[i] 의 child 노드들이가지는 capacity의합이다. 로우측 child와비교하게되고현재 F값이 9이므로입력값 6과자리를바꾸고 9는다시 4-레벨로이동하여빈공간에채워지게된다. Parent 노드에서 child 노드로이동시 parent 노드의 capacity는 1만큼감소하게된다. (3) 내장레지스터의종류및크기 큐매니저에내장된레지스터는다음과같다. Operation register: 우선순위큐의동작을정의하는명령어저장장소. 현재는 enqueue와 dequeue, optimize 3개의명령어를지원하므로 2비트의크기를갖는다. Value register: 우선순위큐 read/write 값으로크기는 2*log2Npq+ log2max(f) 비트이다. Level register: 우선순위큐제어기에의해처리중인우선순위큐의레벨값으로크기는 log2(npq+1) 비트이다. Space counter register: 우선순위큐의전체빈공간수로서 1-레벨큐정보의 capacity 값과같다. (4) 우선순위큐의동작 ( 명령어기준 ) Enqueue Enqueue는큐에새로운노드정보를추가하는것을의미한다. 큐에새로운 F값 6이입력되는예를들어 enqueue 동작을그림 5에서설명하겠다. 신규값 6은 1-레벨노드의 F값 2와비교하여더크므로 2-레벨로이동한다. 이동시에는항시좌측 child 값부터비교하며기준값은 F와 capacity이다. 2-레벨좌측 child의경우 5이며 capacity가 1이므로입력값 6은다시한단계밑으로이동한다. 3-레벨에서좌측 child는 capacity가 0이므로이동이불가능하므 Dequeue 그림 5. Enqueue 동작 Fig. 5. Enqueue operation Dequeue는 1-레벨큐값을읽고해당정보를큐에서삭제하는동작을의미한다. Parent 노드가삭제되면 child 노드의값이 parent 노드로이동하게되며이때 child 노드의 capacity는 1씩증가하게된다. 이해를돕기위해하기그림의예를참조하기바란다. Optimize Optimize는큐에저장된정보중 Node_ID가같은노드들의 F값을비교하여더크거나같은노드를큐에서삭제하는동작을의미한다. 상기동작의필요성은추후설명하도록한다. 3.3 우선순위큐를사용한 A* 알고리즘 그림 1의 A* 알고리즘을분석하면실제많은시간이걸리는부분은 Closed list보다매우큰 Open

5 우선순위큐를이용한 A* 기반최단경로탐색기법 5 list에서가장작은 F값을가지는노드 x를고르는동작 ( 그림 1의라인 8) 과선택된노드 y와 Open list 내같은노드존재여부를확인하고이를비교하는동작 ( 라인 17-23) 이다. 다. 그이유는 A* 에서중복저장되는노드들은보통노드간교차지점에서만발생하기때문에그수가전체노드에비해현저히적고 dequeue 동작으로선택된현재노드 x의 Closed list 존재여부를검사하여존재할경우선택된노드를무시하고다시선택 (dequeue) 하면동일노드의중복저장문제를해결할수있기때문이다. 다시말하면, Open list에중복저장된같은 Node_ID 노드들중 F값이가장작은노드가상위레벨에위치하기때문에먼저 dequeue되어 Closed list에포함될것이며이후 dequeue되는중복노드는 Closed list에추가될수없기때문에전체성능은그대로유지하면서알고리즘을크게간소화할수있다. 그림 7에서우선순위큐를사용한 A* 알고리즘의유사코드를나타내었다. 그림 6. Dequeue 동작 Fig. 6. Dequeue operation 일반적으로우선순위큐를이용한데이터쓰기 / 읽기속도는 O(logN) 이다 (N은전체노드수 ). 그러나 Open list로우선순위큐를사용하게되면실제동작속도는 O(1) 에비례하게된다. 그이유는 A* 하드웨어의경로탐색기에서요구하는노드데이터를 enqueue, dequeue하는데필요한시간은 O(1) 이며이후큐데이터를재정렬하는동작은경로탐색기와병렬적으로우선순위큐매니저내에서동작하기때문이다. 큐의재정렬시간은길어야 O(logN) 을넘지않으므로경로탐색기의데이터처리시간을고려하면이로인한데이터지연문제는거의발생하지않는다고볼수있다. 따라서그림 1의라인 8 은단한번의큐읽기동작으로처리될수있다. 그러나, F값을기준으로정렬된큐에서 Node_ID가동일한노드를검색하는라인 17-23의동작은일반큐와마찬가지로모든노드를차례대로검색해야하므로우선순위큐를사용한장점이사라지게된다. 상기문제를해결하기위해본논문에서는 Node_ID가동일한노드들을검색하는동작을삭제하고동일노드의 Open list 중복저장을허용하였 그림 7. 우선순위큐를사용한 A* 알고리즘의유사코드 Fig. 7. Pseudocode of A* algorithm using priority queue 3.4 우선순위큐의최적화 Node_ID가같은노드의중복저장으로인한큐의저장영역증가문제를해결하기위하여 A* 의부기능으로큐의저장된 Node_ID를검사하여중복된노드가있는경우최상위레벨노드를제외한나머지는삭제하는기능을추가하였다 (3.2절 optimize 명령어참조 ). Optimize는우선순위큐매니

6 6 韓國情報技術學會論文誌제 8 권제 8 호 2010 년 08 월 저의내장레지스터중 Space counter register를읽어서전체노드수대비 capacity가사전정해진값보다작아지면실행되는자동모드와사용자가직접입력한명령어에의해실행되는수동모드로구분할수있다. Ⅳ. 성능평가 (64개) 대비 100% 이상까지증가하였다. 그러나상기문제는적절한 optimize 동작으로쉽게해결될수있다. 그리고맵특성에따라실제값은다소차이가있겠지만평균큐사용량은전체노드수대비 15% 정도로측정되었다. 또한교차노드수에비례하여증가하지만그폭은그리크지않은것으로확인되었다. 본연구에서제안한알고리즘은 C기반시뮬레이터를이용하여기존 A* 알고리즘과비교하였다. 실험에사용된노드는 64개의노드로구성된합성맵이며노드간링크길이와노드의좌표정보가포함되어있다. 노드간링크는양방향이며양방향모두동일크기로간주하였다. 실험방법은임의로시작노드와목적노드를입력하여 A* 알고리즘과제안된알고리즘의경로탐색결과를비교하는형태이다. 총 1000회에걸친시작 / 목적노드대상실험결과모든경우에서두알고리즘의최종선택경로는일치하였고중간경유노드는일부차이 ( 약 3% 정도 ) 가발생하였는데분석결과 Open list에서동일한 F값을갖는노드중어떤것을임시현재노드로선택하는가하는방법차이인것이확인되었다. 우선순위큐에서는동일한 F값일경우좌측 child에저장된노드에우선권을주었지만 A* 알고리즘에서는가장먼저저장된노드가우선하기때문이다. 큐의중복노드저장이전체성능에미치는영향을조사하기위하여실험맵의교차노드수대비큐사용량을비교해보았다 ( 표 1 참조 ). 교차노드는하나의노드에서이웃노드에연결된링크의수가전체평균값이상인것으로정의하였고본실험에서사용된맵에포함된노드링크수는 1~6개이므로 4개이상의링크를가진노드가교차노드가된다. 표 1은교차노드수를변화해가며임의시작 / 목적노드형태로 1000회반복실험을통해서얻어진실험결과이다. 노드당평균링크수는하나의노드가갖는평균링크수이며평균 retry 수는시작노드에서목적노드로이동하는동안발생하는평균재검색횟수 ( 그림 7의라인 11, 12) 이다. 실험결과를보면교차노드수와비례하여 optimize를하지않은상태의최대큐사용량은전체노드수 표 1. 실험맵의교차노드수대비큐사용량 Table 1. The amount of consumed queue against the number of intersection node in the experimental map 교차노드수 노드당평균링크수 평균 retry 수 최대큐사용량 평균큐사용량 Ⅴ. 결론 본논문에서는최단경로탐색을고속으로실행하기위한하드웨어개발을목표로우선순위큐를사용한 A* 알고리즘및관련구조를제안하였다. 시뮬레이션결과기존 A* 와동일한성능을유지하면서도하드웨어구현을위한병렬처리구조에적합함을확인할수있었다. 그러나본실험결과에서도볼수있듯이일정크기이상의큐는전체성능향상에도움이되지않기때문에 [3] 무조건전체노드수만을고려하여큐의크기를할당하는것보다검색노드의특성을고려하여전체큐의크기를설정하는것이알고리즘의성능및하드웨어개발효율성을크게증가시킬수있을것이다. 따라서향후우선순위큐의최적크기선정을위한연구를진행할예정이다. 참고문헌 [1] G. A. Klunder, H.N. Post, The Shortest Path

우선순위큐를이용한 A* 기반최단경로탐색기법 7 Problem on Large-Scale Real-Road Networks, Networks, Vol. 48, Issue 4, pp. 182-194, Dec., 2006. [2] 신용욱, 양태용, 백원장, 복수경로탐색을위한휴리스틱알고리즘에대한연구, 한국산업공학회저널, 32권, 3호, pp.

Gokhale, On the Acceleration of Shortest Path Calculations in Transportation Networks, International Symposium on Field-Programmable Custom Computing Machines, pp. 23-32, 2007.

Conference on Communications, 2007. [5] http://en.wikipedia.org/wiki/a*_search_algorithm. [6] A. Ioannou and M. G. H.

7 우선순위큐를이용한 A* 기반최단경로탐색기법 7 Problem on Large-Scale Real-Road Networks, Networks, Vol. 48, Issue 4, pp , Dec., [2] 신용욱, 양태용, 백원장, 복수경로탐색을위한휴리스틱알고리즘에대한연구, 한국산업공학회저널, 32권, 3호, pp , 2006년 9 월. [3] Z. K. Baker and M. Gokhale, On the Acceleration of Shortest Path Calculations in Transportation Networks, International Symposium on Field-Programmable Custom Computing Machines, pp , [4] Hiroyuki Ishikawa, Sho Shimizu, Yutaka Arakawa, Naoaki Yamanaka, Kosuke Shiba, New Parallel Shortest Path Searching Algorithm based on Dynamically Reconfigurable Processor DAPDNA-2, International Conference on Communications, [5] [6] A. Ioannou and M. G. H. Katevenis, Pipelined Heap (Priority Queue) Management for Advanced Scheduling in High-Speed Networks, IEEE/ACM Trans. on Networking, Vol. 15, No. 2, April, [7] R. Bhagwan and B. Lin, Fast and Scalable Priority Queue Architecture for High-Speed Network Switches, in Proc. IEEE INFOCOM, Vol. 2, pp , Mar., 저자소개안진호 (Jin-Ho Ahn) 1995년 2월 : 연세대학교전기공학과 ( 공학사 ) 1997년 2월 : 연세대학교전기공학과 ( 공학석사 ) 2002년 8월 : 엘지전자 DTV연구소연구원 2006년 8월 : 연세대학교전기전공학과 ( 공학박사 ) 2007년 3월 ~ 현재 : 호서대학교전자공학과교수관심분야 : SOC 설계및응용, 테스트 박민지 (Min-Ji Park) 2009년 2월 : 호서대학교전자공학과 ( 공학사 ) 2009년 3월 ~ 현재 : 호서대학교전자공학과석사과정관심분야 : 디지털시스템설계및응용강성호 (Sungho Kang) 1986년 : 서울대학교제어계측공학과 ( 공학사 ) 1988년 : The University of Texas, Austin 전기및컴퓨터공학과 ( 공학석사 ) 1992년 : The University of Texas, Austin 전기및컴퓨터공학과 ( 공학박사 ) 1992년 : 미국 Schlumberger 연구원 1994년 : 미국 Motorola 선임연구원현재 : 연세대학교전기전자공학과교수관심분야 : SOC 설계및테스트문병인 (Byungin Moon) 1995년 2월 : 연세대학교전자공학과 ( 공학사 ) 1997년 2월 : 연세대학교전자공학과 ( 공학석사 ) 2002년 2월 : 연세대학교전기전자공학과 ( 공학박사 ) 2002년 ~ 2004년 : 하이닉스반도체선임연구원 2004년 ~ 2005년 : 연세대학교연구교수 2005년 ~ 현재 : 경북대학교전자공학부조교수관심분야 : SoC, 디지털 VLSI, 컴퓨터구조

Microsoft PowerPoint - 30.ppt [호환 모드]

Microsoft PowerPoint - 30.ppt [호환 모드] 이중포트메모리의실제적인고장을고려한 Programmable Memory BIST 2010. 06. 29. 연세대학교전기전자공학과박영규, 박재석, 한태우, 강성호 hipyk@soc.yonsei.ac.kr Contents Introduction Proposed Programmable Memory BIST(PMBIST) Algorithm Instruction PMBIST