2007 년 10 월전자공학회논문지제 44 권 SD 편제 10 호 55 논문 2007-44SD-10-8 패킷스케줄러를위한빠르고확장성있는 우선순위큐의하드웨어구조 (A Fast and Scalable Priority Queue Hardware Architecture for Packet Schedulers ) 김상균 *, 문병인 ** 1 (Sanggyun Kim and Byung In Moon ) 요 약 본논문에서는 QoS 를보장하면서빠른네트워크속도를지원해줄수있는우선순위큐의구조를제안한다. 제안한큐의구조는하나의큐로여러개의출력부에출력을보낼수있어면적을줄일수있고, 제어블록을추가함으로써기존의 multiple systolic array 우선순위큐보다더빠른속도로동작할수있기때문에높은패킷처리속도를요구하는패킷스케줄러등에적합한구조이다. 또한, 이구조는높은확장성을지원한다. Abstract This paper proposes a fast and scalable priority queue architecture for use in high-speed networks which supports quality of service (QoS) guarantees. This architecture is cost-effective since a single queue can generate outputs to multiple out-links. Also, compared with the previous multiple systolic array priority queues, the proposed queue provides fast output generation, which is important to high-speed packet schedulers, using a special control block. In addition, this architecture provides the feature of high scalability. Keywords : Quality of Service, Priority Queue, Packet Scheduler Ⅰ. 서론 요즘많이이용되고있는실시간동영상이나실시간음악서비스등의 real-time 통신에서는기존의웹서핑과같은일반적인통신보다높은속도와 QoS(Quality of Service) 의보장을요구한다. QoS란사용자또는어플리케이션의중요도에따라서비스수준을차등화하여한정된대역폭에서트래픽과대역폭을정책적으로관리하는것을말한다. 즉, 끊김이없는동영상을보거 * 학생회원, ** 평생회원, 경북대학교전자전기컴퓨터학부 (School of Electrical Engineering & Computer Science, Kyungpook National University) 이논문은 2005년도경북대학교학술진흥연구비에의하여연구되었음. 접수일자 : 2007년5월26일, 수정완료일 : 2007년9월21일 나음악을듣기위해서는 QoS가보장되어야한다. 이전의네트워크장비들은 QoS를보장하기위해소프트웨어적인기술들을사용하였으나근래의높아진네트워크의속도에맞춰 QoS를보장하기위해서는하드웨어적인기술이필요하다. QoS를보장하기위한하드웨어구조로각데이터에알맞은우선순위를부여하고높은우선순위순으로데이터를처리하는방법이가장많이사용되고있다. 예를들면, binary tree based of comparator 우선순위큐 [4], shift register 우선순위큐 [1], systolic array 우선순위큐 [2~3] 등이있다. 하지만이런방법들은결점이존재한다. binary tree based of comparator 우선순위큐의경우큐의용량이늘어남에따라출력이나오는시간이지연된다. shift register 우선순위큐와 systolic (885)
56 패킷스케줄러를위한빠르고확장성있는우선순위큐의하드웨어구조김상균외 array 우선순위큐는확장성은만족하지만여러개의출력부를사용할때는면적이커지는단점이있다. 본론에서소개할 modified multiple systolic array 우선순위큐는위에서말한우선순위큐의단점들을보안한구조로여러개의출력부를가지고높은속도를요구하는패킷스케줄러에알맞은우선순위큐이다. Ⅱ. 본론 1. 여러우선순위큐의구조들현재사용되고있는여러우선순위큐의구조들에대해알아보고각각의장단점을파악해보자. 가. Shift Register 우선순위큐 Shift register 우선순위큐는그림 1과같은구조로각블록들이바로옆 ( 좌, 우 ) 블록들과서로연결되어있다. [1] 입력된데이터는버스를통해모든블록에동시에입력되고우선순위를비교하여한블록만데이터를저장하고나머지블록의데이터들은오른쪽또는왼쪽으로순차적으로이동하게된다. 가장오른쪽블록에가장높은우선순위를가지는데이터가항상존재하므로읽기신호가들어오면가장오른쪽블록의데이터가출력된다. 하지만입력되는데이터가모든블록에동시에입력되어야하기때문에블록들이많아지면버스로딩문제가발생하게된다. 그림 2. Systolic array 우선순위큐의구조 Fig. 2. Structure of the systolic array priority queue. 지게된다. 하지만각블록의내부를보면저장하는레지스터와우선순위비교후왼쪽블록으로보낼레지스터두개를가지므로 shift register 우선순위큐보다는많은면적을차지한다. 다. Modified Systolic Array 우선순위큐위에서설명한두우선순위큐의장점을모아서 modified systolic array 우선순위큐를구성하였다. [5] 확장성을위해그림 3과같이여러개의 modified systolic array 우선순위큐블록이 systolic array와같은형태로연결되어있고각블록의내부는 shift register와같은구조를가지고있다. shift register 내부에연결되어있는블록들은버스로딩문제를일으키지않을만큼의수만큼만연결한다. 그림 1. Shift register 우선순위큐의구조 Fig. 1. Structure of the shift register priority queue. 나. Systolic Array 우선순위큐 Systolic array 우선순위큐는그림 2와같이 shift register 우선순위큐와비슷한구조를가지고있다. [2~3] 하지만모든블록에동시에입력되는것이아니라가장오른쪽블록이입력을받고우선순위에따라데이터가왼쪽으로이동한다. shift register 우선순위큐와같이가장오른쪽블록이가장높은우선순위의데이터를가 그림 3. Modified systolic array 우선순위큐의구조 Fig. 3. Structure of the modified systolic array priority queue. 라. Multiple Systolic Array 우선순위큐위에서설명한 modified systolic array 우선순위큐를이용하여여러개의출력부를하나의큐로대체할수있는 multiple systolic array 우선순위큐를그림 4 와같이구성하였다. [5] 기존의여러큐구조에서는각각의출력부에큐가하나씩있어야했으나이구조를이용하면하나의큐로여러개의출력부로출력을보낼수있으므로면적이절약이된다. 기본적인구조는 (886)
2007 년 10 월전자공학회논문지제 44 권 SD 편제 10 호 57 고빠른속도로입출력을하기위해추가된블록으로각 shift register 블록들에연결되어있다. 확장성을만족시켜주기위해그림5와같이 systolic array의형태로여러개의 modified multiple systolic array 우선순위큐를연결한다. 나. 동작 그림 4. Multiple systolic array 우선순위큐의구조 Fig. 4. Structure of the multiple systolic array priority queue. modified systolic array 우선순위큐와비슷하지만여러출력부에데이터를보낼수있도록하기위해몇가지블록들이추가되어있다. 2. Modified Multiple Systolic Array 우선순위큐 기존의 multiple systolic array 우선순위큐는각출력부에대한입력과출력에여러사이클이소요된다. 데이터가입력되면한블록에만저장되고나머지블록의데이터들은순차적으로이동하기때문에데이터가정렬될때까지기다린뒤출력하거나, 이동중인데이터를제외하고저장되어있는데이터중가장높은우선순위의데이터를출력하게된다. 즉, 출력하는데시간 이많이걸리거나잘못된데이터가출력될수도있다. 우리는제어를위한블록을추가하여이문제를해결할수있는새로운구조를제안한다. 가. 제안하는구조 그림 5와같이내부각블록들이서로연결되어있는구조는 multiple systolic array 우선순위큐와같지만제어블록이추가되어있다. 제어블록은좀더정확하 각블록들은제어블록의신호에따라 read, write, shift_right, shift_left 의네가지동작을한다. 기존의 multiple systolic array 우선순위큐는 shift register 의각블록에동시에데이터가입력되어각블록에서우선순위를판단한뒤저장하거나오른쪽또는왼쪽으로데이터를보낸다. 하지만 modified multiple systolic array 우선순위큐는제어블록이어느블록에데이터를쓸것인가와어느블록으로부터읽을것인가를판단하여각블록에신호를보낸다. 순차적으로데이터가이동되는것이아니라한꺼번에이동되므로빠르게입출력이가능하다. (1) 입력데이터가입력되면제어블록에서데이터가저장될블록을파악하여해당블록에 write 신호를보내고그왼쪽블록들중출력부번호가다른블록에는동시에 shift_left 신호를보내저장되어있던데이터를한블록씩왼쪽으로이동시킨다. 그림 6의 (b) 를보면, (a) 의정렬된상태에서출력부번호 1을가진 data가입력이된다. data가입력될블록은 write 신호가입력이되고, 나머지왼쪽블록들에게는 shift left 신호가입력이되어 1 cycle 후에는그림과같이정렬이된다. 그림 5. Modified multiple systolic array우선순위큐의구조 Fig. 5. Structure of the modified multiple systolic array priority queue. (887)
58 패킷스케줄러를위한빠르고확장성있는우선순위큐의하드웨어구조김상균외 (a) 정렬된상태 그림 7. 제어블록의구조 Fig. 7. Structure of the control block. (b) 출력부번호 1 을가진 data 입력 출력부의개수만큼포인터도존재하므로각출력부의가장높은순위의데이터를가진블록위치를가리키고있다. 이것은출력시에이용된다. 시그널컨트롤러는각포인터와카운터의값, 입력으로들어오는 write, read 신호를받아서어느블록에 shift_right, shift_left, write, read 신호를보낼지결정하는역할을한다. (c) 출력부번호 0을가진데이터출력그림 6. 입출력동작예시 Fig. 6. Examples of input and output operations. (2) 출력출력신호가들어오면해당출력부번호를가지는데이터들중가장순위가높은블록이 read 신호를받아데이터를출력시키고나머지왼쪽블록들은 shift_right 신호를받아데이터를한블록씩오른쪽으로이동시킨다. 그림 6의 (c) 를보면, 출력부 0을가진 data의출력을요청하는신호가입력되면가장오른쪽블록에 read 신호가입력되고나머지왼쪽의블록들은 shift right 신호를입력받아 1 cycle 후정렬이된다. 다. 제어블록제어블록은그림 7과같이포인터, 카운터그리고시그널컨트롤러로구성되어있다. 카운터와포인터는출력부의수만큼존재한다. 카운터는저장되어있는데이터의수를헤아리고있다가데이터가없을경우, 연결되어있는 modified multiple systolic array 블록에해당출력부의데이터를요구한다. 포인터는저장되어있는데이터중가장우선순위가높은데이터가저장되어있는블록을가리킨다. Ⅲ. 실험본논문에서제안한 modified multiple systolic array 우선순위큐는 RTL수준으로구현하여시뮬레이션및합성하였다. 기존의우선순위큐들과의크기를비교하기위하여, 앞에서소개한 shift register 우선순위큐, systolic array 우선순위큐, modified systolic array 우선순위큐, multiple systolic array 우선순위큐의저장소크기를 32개로정하고합성한후, modified multiple systolic array 우선순위큐와 transistor의수를비교하였다. 그림8과같이출력부가한개일때는 multiple systolic array 우선순위큐와 modified multiple systolic array 우선순위큐의면적이크지만출력부의수가많아질수록 shift register 우선순위큐, systolic array 우선순위큐그리고 modified systolic 우선순위큐는출력부의수에비례하여면적이넓어지는반면 multiple systolic array 우선순위큐와 modified multiple systolic array 우선순위큐는출력부의수와상관없이일정한크기를가진다. 대부분의패킷스케줄러는 1개이상의출력부를가지기때문에 multiple systolic array 우선순위큐와 modified multiple systolic array 우선순위큐는기존의다른우선순위큐 (888)
2007 년 10 월전자공학회논문지제 44 권 SD 편제 10 호 59 으로써더빠른속도로동작함을확인할수있었다. 이결과는각각의블록이데이터의우선순위를판단하여정렬하는 multiple systolic array 우선순위큐보다제어블록을이용하여데이터를입출력하는 modified multiple systolic array 우선순위큐가좀더빠른성능을나타낸다고할수있다. 또한 ISE를이용하여합성한결과제어장치는전체 modified multiple systolic array 우선순위큐면적의 5% 만차지함을알수있었다. Ⅳ. 결론 그림 8. Modified multiple systolic array 우선순위큐와 기존의큐들의 transistor 수의비교 Fig. 8. Comparison of the number of transistors used in modified multiple systolic array priority queue and the previous priority queues. 표 1. 출력부의수를다르게했을경우, 입출력에걸리는 cycle 수비교 Table 1. Comparison of input/output cycle counts (for a single output links and four output links) by changing out-link numbers. 출력부개수 1개 4개 큐의구조 ( 입력 / 출력 ) ( 입력 / 출력 ) multiple systolic array 우선순위큐 5 / 7 cycle[5] 5 / 7 cycle [5] modified multiple systolic array 우선순위큐 1 / 1 cycle 1 / 1 cycle 보다면적에서효율적인구조이다. Multiple systolic array 우선순위큐와 modified multiple systolic array 우선순위큐의성능을비교하기위해서출력부가 1개일때와 4개일경우를구분하여시뮬레이션하였다. 아래의표 1은하나의 modified multiple systolic array 우선순위큐블록만을사용하였을때의경우이다. 만약, 확장을위해 modified multiple systolic array 우선순위큐블록을더연결한다면입력과출력에걸리는 cycle은연결한블록의수만큼늘어나게된다. Multiple systolic array 우선순위큐와 modified multiple systolic array 우선순위큐를비교했을때, 표 1과같이출력부의수가달라져도입출력 cycle은변함이없는것은동일했지만, modified multiple systolic array 우선순위큐가입출력모두에 1 cycle만소요됨 본논문은패킷스케줄러를위한빠르고확장성있는우선순위큐의하드웨어구조를제안하였다. 출력부가여러개일경우기존의여러우선순위큐보다적은면적으로높은성능을낼수있었으며, multiple systolic array 우선순위큐의단점을보완하기위하여제어블록을추가적으로두어, 좀더빠르고정확한동작을할수있도록하였다. 실험을통해적은면적의제어블록을추가한 modified multiple systolic array 우선순위큐가 multiple systolic array 우선순위큐보다빠르게동작함을확인할수있었다. 참고문헌 [1] J. Chao, A Novel Architecture for Queue Management in the ATM network, IEEE J. Selected Areas in Comm. vol. 9, no. 7, pp. 1,110-1,118, Sept. 1991. [2] P. Lavoie and Y. Savaria, A Systolic Architecture for Fast Stack Sequential Decoders, IEEE Trans. Comm, vol. 42, nos. 2/3/4, pp. 324-334, Feb./Mar/Apr. 1994. [3] C.E. Leiserson, Systolic Priority Queues, Proc. Caltech Conf. VLSI, pp. 200-214, Jan. 1979. [4] D. Picker and R. Fellman, A VLSI Priority Packet Queue with Inheritance and Overwrite, IEEE Trans. Very Large Scale Integration Systems, vol. 3 no. 2, pp. 245-252, June. 1995. [5] S. Moon, J. Rexford, and K. Shin, Scalable Haradware Priority Queue Architectures for High-Speed Packet Switches, IEEE Trans. Comp, vol. 49, no. 11, pp. 1215-1226. Nov. 2000. (889)
60 패킷스케줄러를위한빠르고확장성있는우선순위큐의하드웨어구조김상균외 저자소개 김상균 ( 학생회원 ) 2006 년경북대학교전자전기컴퓨터학부학사졸업 2007 년현재경북대학교전자공학과석사과정 < 주관심분야 : 네트워크프로세서설계 > 문병인 ( 평생회원 ) 1995 년연세대학교전자공학과학사졸업 1997 년연세대학교전자공학과석사졸업. 2002 년연세대학교전기전자공학과박사졸업. 2002 년 ~2004 년하이닉스반도체선임연구원 2004 년 ~2005 년연세대학교연구교수 2005 년 ~ 현재경북대학교전자전기컴퓨터학부조교수 < 주관심분야 : 디지털집적회로설계, SoC 설계, 마이크로프로세서구조설계 > (890)