다단계 계층적 큐빅 네트워크

윤상균(Sang-Kyun Yun) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.5

하이퍼큐브는 그것이 지닌 여러 장점 때문에 가장 널리 시용되는 연결망 구조중 하나이지만 노드수가 증가함에 따라서 구현하기 어려울 정도로 랭크 갯수가 증가한다. 이러한 하이펴큐브의 단점을 보완하여 링크 수가 적으면서도 하이퍼큐브와 마찬가지의 병렬 알고리즘 성능을 보이며 오히려 적은 지름을 갖는 하이퍼큐브에 기초하여 구성된 계층적 큐빅 네트웍(HCN)이 Ghose와 Desai 에 의해서 제안되었다. 이 논문에서는 대규모 병렬 시스템 구성에 적합한 HCN의 확장된 연결망인 다단계 계층적 큐빅 네트웍(MHCN)을 제안한다. 이 연결망은 하이퍼큐브보다 적은 링크 수를 갖는다. 2^k개의 노드를 갖는 네트웍을 구성할 때에 하이퍼큐브는 노드당 K개의 링크를 갖는 데 비해서 MHCN은 약 2√k의 링크를 갖는다. 또한 MHCN은 적은 링크 수에도 불구하고 많은 병렬 알고리즘을 하이퍼큐브와 마찬가지의 시간 복잡도로 수행할 수 있다. The hypercube is one of the most widely used topologies because it provides small diameter and embedding of various interconnection networks. For very large systems, however, the number of links needed with the hypercube may become prohibitively large. Hierarchical cubic network(HCN) proposed by Ghose and Desai is an interconnection network which has the smaller number of links, the smaller diameter, and the same time complexity of many parallel algorithms in comparison with the hypercube. In this paper, we propose a hierarchical interconnection network based on hypercubes called multilevel hierarchical cubic network (MHCN) for massively parallel computers, which is the extension of the HCN. The MHCN has a smaller number of links than the comparable hypercube and in particular, when we construct networks with 2^k nodes, the node degree of MHCN with the minimum node degree is about 2√K while that of hypercube is K. Regardless of its smaller node degree, many parallel algorithms can be executed in MHCN with the same time complexity as in the hypercube.

NIDS를 위한 다중바이트 기반 정규표현식 패턴매칭 하드웨어 구조

윤상균(SangKyun Yun),이규희(KyuHee Lee) 한국통신학회 2009 韓國通信學會論文誌 Vol.34 No.1B

최근의 네트워크 침입탐지 시스템에서는 침입이 의심되는 패킷을 나타내는 데 정규표현식이 사용되고 있다. 고속 네트워크를 통해서 입력되는 패킷을 실시간으로 검사하기 위해서는 하드웨어 기반 패턴 매칭이 필수적이며 변화되는 패턴 규칙을 다루기 위해서는 FPGA와 같은 재구성 가능한 디바이스를 사용하는 것이 바람직하다. FPGA의 동작 속도 제한으로 바이트 단위의 패킷 검사로는 실시간 검사를 할 수 없는 경우에 이를 해결하기 위해서 여러 바이트 단위로 검사하는 것이 필요하다. 본 논문에서는 정규표현식 패턴 매칭을 n바이트 단위로 처리하는 하드웨어의 구조와 설계 방법을 제시하고 이에 대한 패턴 매칭 회로 생성기를 구현한다. Snort 규칙에 대해 FPGA로 합성된 하드웨어는 n=4일 때에 규칙에 따라서 2.62~3.4배의 처리 속도 향상을 보였다. In recent network intrusion detection systems, regular expressions are used to represent malicious packets. In order to process incoming packets through high speed networks in real time, we should perform hardware-based pattern matching using the configurable device such as FPGAs. However, operating speed of FPGAs is slower than giga-bit speed network and so, multi-byte processing per clock cycle may be needed. In this paper, we propose a hardware architecture of multi-byte based regular expression pattern matching and implement the pattern matching circuit generator. The throughput improvements in four-byte based pattern matching circuit synthesized in FPGA for several Snort rules are 2.62~3.4 times.

심층 패킷검사를 위한 정규표현식 패턴매칭 하드웨어 구조

윤상균(Sang-Kyun Yun),이규희(Kyu-Hee Lee) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.5

최근의 네트워크 침입탐지 시스템들은 침입패턴을 나타내는 데 정규표현식을 사용하고 있으며 빠른 심층 패킷 검사를 위해서 하드웨어 기반의 패턴매칭이 필요하다. 하드웨어 기반 정규표현식 패턴매칭에 대한 많은 연구가 이루어졌으나 {10}과 같은 제한반복 연산자에 대한 구현은 제약이 있었다. 본 논문에서는 일반적인 정규표현식 서브패턴에 대한 제한반복을 더 낮은 하드웨어 복잡도로 구현할 수 있는 제한반복 블록 구조를 제시하였다. 제안된 제한반복 블록은 단일 문자, 고정길이 문자 뿐 만 아니라 일반적인 정규표현식 서브패턴의 제한반복 구현도 가능하다. 제안된 제한반복 블록 구조는 모든 제한반복을 펼치지 않고 구현할 수 있도록 하여 정규표현식 패턴매칭 하드웨어를 더 효율적으로 구현할 수 있도록 하였다. Network Intrusion Detection Systems use regular expression to represent malicious packets and hardware-based pattern matching is required for fast deep packet inspection. Although hardware architectures for implementing constraint repetition operators such as {10} were recently proposed, they have some limitation. In this paper, we propose hardware architecture supporting constraint repetitions of general regular expression sub-patterns with lower logic complexity. The subpatterns supported by the proposed contraint repetition architecture include general regular expression patterns as well as a single character and fixed length patterns. With the proposed building block, we can implement more efficiently regular expression pattern matching hardwares.

SoC FPGA에서의 정규표현식 프로세서를 위한 호스트 인터페이스 설계

윤상균(SangKyun Yun),김경민(KyungMin Kim),이규희(KyuHee Lee) 한국통신학회 2015 한국통신학회 학술대회논문집 Vol.2015 No.06

문자클래스 매칭을 지원하는 정규표현식 매칭 프로세서 구조

윤상균(SangKyun Yun) Korean Institute of Information Scientists and Eng 2015 정보과학회논문지 Vol.42 No.10

Many hardware-based regular expression matching architectures are proposed for high performance matching. In particular, regular expression processors such as ReCPU and SMPU perform pattern matching in a similar approach to that used in general purpose processors, which provide the flexibility when updating patterns. However, these processors are inefficient in performing class matching since they do not provide character class matching capabilities. This paper proposes an instruction set and architecture of a regular expression matching processor, which can support character class matching. The proposed processor can efficiently perform character class matching since it includes character class, character range, and negated character class matching capabilities.

협동 병렬 X-Match 데이타 압축 알고리즘

윤상균(Sang-Kyun Yun) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.9·10

X-Match 알고리즘은 비교적 간단하여 하드웨어로 구현하는 데에 적합한 무손실 압축 알고리즘이다. X-Match 알고리즘은 사이클 당 32비트의 압축이 가능하므로 고속 압축에 적합하다. 그렇지만 버스 폭이 증가됨에 따라서 이에 맞추어서 압축 단위를 증가시킬 필요가 있게 되었다. 본 논문에서는 X-Match 알고리즘을 병렬로 수행하여 압축 속도를 2배 향상시키고 X-Match 알고리즘 거의 비슷한 압축률을 제공하는 협동 병렬 X-Match 알고리즘, 즉 X-MatchCP 알고리즘을 제안한다. 기존의 병렬 X-Match 알고리즘이 X-Match 알고리즘을 병렬로 수행할 때에 각자의 사전을 검색하는 데 비해서 X-MatchCP 알고리즘에서는 X-Match 알고리즘이 병렬로 수행되지만 전체 사전을 검색하여 매칭빈도를 높이도록 하였고 run-length 부호화도 두 워드에 대해서 한꺼번에 하는 방식으로 서로 협동하면서 동작한다. 메모리 데이타와 파일 자료를 사용한 시뮬레이션 결과 X-MatchCP 알고리즘은 같은 사전 크기의 X-Match 알고리즘과 거의 비슷한 압축률을 보였다. 그리고 X-MatchCP 알고리즘의 하드웨어 구현을 위한 전체적인 구조 설계를 Verilog 언어를 사용하여 수행하였다. X-Match algorithm is a lossless compression algorithm suitable for hardware implementation owing to its simplicity. It can compress 32 bits per clock cycle and is suitable for real time compression. However, as the bus width increases 64-bit, the compression unit also need to increase. This paper proposes the cooperative parallel X-Match (X-MatchCP) algorithm, which improves the compression speed by performing the two X-Match algorithms in parallel. It searches the all dictionary for two words, combines the compression codes of two words generated by parallel X-Match compression and outputs the combined code while the previous parallel X-Match algorithm searches an individual dictionary. The compression ratio in X-MatchCP is almost the same as in X-Match. X-MatchCP algorithm is described and simulated by Verilog hardware description language.

메쉬에서의 채널 트래픽 분포의 분석

윤상균(Sang Kyun Yun) 서원대학교 미래창조연구원 1998 응용과학연구 Vol.7 No.1

Multilevel Hierarchical Cubic Networks

Sang-Kyun Yun(윤상균) 서원대학교 미래창조연구원 1997 응용과학연구 Vol.6 No.1

열전소자를 이용한 냉풍조끼 제작

윤상국(Sang-kuk Yun),이지훈(Ji-hun Lee),최일걸(Il-gul Choi),강민균(Min-gyun Kang),김보성(Bo-sung Kim),정일영(Il-young Jeong),박은주(Eun-ju Park) 한국항해항만학회 2008 한국항해항만학회 학술대회논문집 Vol.2008 No.공동학술

Respects workers who work from the interior must accomplish the industrial site of the sultry summer season or the work of high temperature and work own directness to wear on the air conditioner outside of site directness is cool in the work person and wishes to swell up the possibility of decreasing in order to be, is a chilly wind vest which made. With the work voluntary service environmental improvement which wears the item which sees about reduction is comfortable from shop floor to feel and in order will be able to enhance the effectiveness of production, there is a goal of the work.

하드웨어 기란 집합연관 IP 주소 검색 방식

윤상균,Yun Sang-Kyun 한국통신학회 2005 韓國通信學會論文誌 Vol.30 No.8B

인터넷에서의 통신량이 증가함에 따라서 라우터의 고속 패킷 처리가 요구되며 IP 주소검색 이 라우터의 성능에 커다란 영향을 미친다. 인덱스 방식의 테이블을 사용하는 이전의 하드웨어 기반 IP 주소 검색 방법은 라우팅 프리픽스의 희소 분포로 인해서 메모리를 효율적으로 사용하지 못하여 메모리 요구량을 줄이는 데에 한계가 있다. 본 논문에서는 이전 방식보다 적은 양의 메모리를 가지고도 같은 IP주소 검색 속도를 제공하는 집합연관 IP 주소 검색 방식을 제안한다. 제안된 방식은 NHA 엔트리에 프리픽스와 다음경로 정보를 함께 저장하며 목적지 IP 주소를 연관 집합의 8개의 엔트리와 동시에 비교하여 일치하는 프리픽스를 찾도록 한다. 제안된 방식의 메모리 요구량은 Lin의 방식에 비해서 반 이하로 감소하여 효율적인 하드웨어 기반 If 주소 검색방식임을 입증하였다. IP lookup and forwarding process becomes the bottleneck of packet transmission as IP traffic increases. Previous hardware-based IP address lookup schemes using an index-based table are not memory-efficient due to sparse distribution of the routing prefixes. In this paper, we propose memory-efficient hardware based IP lookup scheme called set-associative IP address lookup scheme, which provides the same IP lookup speed with much smaller memory requirement. In the proposed scheme, an NHA entry stores the prefix and next hop together. The IP lookup procedure compares a destination IP address with eight entries in a corresponding set simultaneously and finds the longest matched prefix. The memory requirement of the proposed scheme is about $42\%$ of that of Lin's scheme. Thus, the set-associative IP address lookup scheme is a memory-efficient hardware based IP address lookup scheme.