분산 실시간 시스템의 설계 공간 탐색을 위한 최악 응답시간 분석 기법

하효진(Hyojin Ha),정연(Yan Zheng),김진우(Jinwoo Kim),하순희(Soonhoi Ha) 한국정보과학회 2013 정보과학회논문지 : 시스템 및 이론 Vol.40 No.3

분산 실시간 시스템에서 정확한 최악 응답시간을 분석하는 것은 시스템의 안정성 측면에서 매우 중요하다. 따라서 시스템의 설계 과정에서부터 최악 응답시간이 데드라인을 만족시키는 것을 검증하는 것이 바람직하다. 그러나 기존의 최악 응답시간 분석법들은 시간이 너무 오래 걸리거나 분석의 정확도가 떨어져 설계 공간 탐색시에 실제로 활용하기에는 무리가 있었다. 본 논문에서는 다목적 유전 알고리즘을 사용하는 최악 응답시간 분석법을 제안하고 그 성능을 실험을 통해 측정하였다. 그 결과 수행시간 대비높은 분석 정확도를 보이는 것을 확인하여 수행시간과 분석의 정확도 사이의 최적 트레이드-오프를 얻을 수 있었다. 그리고 비슷한 정확도를 갖는 기존의 분석법에 비하여 시간 복잡도 측면의 확장성이 좋은 것을 확인하였다. 또한 분석의 부산물로 준-최악 시나리오를 다양하게 제공하여 정확성, 확장성, 빠른 분석시간 외에도 설계 공간 탐색시에 유용하게 사용할 수 있는 특성을 가짐을 볼 수 있었다. Since worst-case response time (WCRT) is critical to the real-time system’s safety, it is important to analyze the exact WCRT before its implementation. So, the design space exploration for distributed real-time system should include WCRT analysis and verify whether it meets the deadline even in WCRT or not. But existing WCRT analysis is not proper for design space exploration because it takes too long or over-estimates the WCRT. This paper presents a WCRT analysis using multi-objective genetic algorithm and shows its performance and characteristics. As a result, this analysis technique showed highly accurate results in relatively short time and achieved the trade-off between accuracy of analysis and analyzing time in existing WCRT analysis. It also has good scalability, when compared with other highly accurate analysis techniques. In addition, the proposed WCRT analysis provides near-worst-case scenarios as a byproduct of the genetic algorithm, which will be useful in design space exploration.

멀티 프로세서 시스템-온-칩(MPSoC)을 위한 버스 매트릭스 구조의 빠르고 정확한 성능 예측 기법 (pp.527-539)

김성찬(Sungchan Kim),하순희(Soonhoi Ha) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.11·12

본 논문은 큐잉 이론을 이용한 멀티 프로세서 시스템-온-칩(MPSoC)의 버스 매트릭스 기반 통신 구조에 대한 성능 예측 기법을 제안한다. 버스 매트릭스 기반 통신 구조는 다양한 설계 인자를 가지고 있어 이에 대한 성능 최적화는 방대한 설계 공간의 탐색을 필요로 하지만, 현재 널리 사용되고 있는 시뮬레이션에 기반한 방법은 많은 시간을 요구하기 때문에 점점 짧아지고 있는 시장 적기 출하(time-to-market) 제약 조건을 만족하기 어렵다. 이러한 문제를 해결하기 위하여 본 논문에서는 시뮬레이션보다 훨씬 빠르면서 정확하게 성능을 예측할 수 있는 기법을 개발하였다. 제안한 성능 분석 기법은 고성능의 버스 매트릭스를 위해 사용되는 버스 프로토콜인 multiple-outstanding transaction을 고려한다. 또한 지수 분포(exponential distribution)를 이용하여 비현실적으로 메모리 시스템을 모델하였던 기존의 연구들과 달리 실제적인 메모리 시스템 모델을 위하여 일반 분포(general distribution)를 이용하였다. 제안한 성능 예측 기법의 정확도 및 효율성을 검증하기 위하여 무작위로 생성된 버스 트랜잭션들과 4-채널 DVR 예제에 적용하였을 때, 사이클 단위의 정확도를 갖는 시뮬레이션과 비교하여 105배 이상 빠르면서 평균 94% 이상의 정확도를 갖는 것으로 분석되었다. This paper presents a performance estimation technique based on queuing analysis for on-chip bus matrix architectures of Multi-Processor System-on-Chips(MPSoCs). Previous works relying on time-consuming simulation are not able to explore the vast design space to cope with increasing time-to-market pressure. The proposed technique gives accurate estimation results while achieving faster estimation time than cycle-accurate simulation by order of magnitude. We consider the followings for the modeling of practical memory subsystem: (1) the service time with the general distribution instead of the exponential distribution and (2) multiple-outstanding transactions to achieve high performance. The experimental results show that the proposed analysis technique has the accuracy of 94% on average and much shorter runtime (105 times faster at least) compared to simulation for the various examples: the synthetic traces and real-time application, 4-channel DVR.

데이타 플로우 명세로부터 직렬화된 멀티태스킹 코드 생성

권성남(Seongnam Kwon),하순희(Soonhoi Ha) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.9·10

갈수록 복잡해지는 임베디드 시스템을 개발하는데 있어서 소프트웨어 개발의 중요성이 점차 커지고 있다. 대부분의 임베디드 응용 소프트웨어는 멀티 태스크로 구성되어 있는 병렬 소프트웨어이며, 기존의 순차적인 프로그래밍 언어만으로 개발하는 것 보다는 알고리즘의 병렬성을 명세하기에 용이한 데이타 플로우 모델로부터 소프트웨어를 생성하는 것이 유망하다. 생성된 멀티태스킹 코드를 수행하기 위해선 태스크들을 병렬적으로 수행해 주고 태스크간 동기화를 담당해 줄 운영체제의 도움이 필요하다. 그러나 운영체제를 사용하기 어려운 환경이나 설계 공간 탐색 과정에서 운영체제를 매번 다양한 하드웨어 플랫폼에 포팅하기 어려운 경우에는 운영체제 없이 멀티 태스크 응용을 수행할 수 있는 방법이 필요하다. 이것을 위해서 이 연구에서는 데이타 플로우 명세로부터 직렬화된 멀티태스킹 코드를 생성하는 방법을 제안한다. 제안하는 방법에서 하나의 태스크는 데이타 플로우 모델로 명세되며, 하나의 C 코드로 생성된다. 코드 생성은 크게 두 단계로 이루어지는데, 먼저 태스크를 구성하는 블록들을 각각 함수 형태로 코드를 생성한 후에, 생성된 여러 태스크의 함수들을 모아서 직렬화하여 호출하는 스케줄러를 만든다. 이 때에 스케줄러를 효율적으로 만들 수 있는 자료구조 및 정보를 제공하여 사용자가 수동으로 스케줄러를 만드는 것도 가능하도록 하였다. DivX예제를 통하여 제안하는 방법으로 생성한 코드가 효율적으로 올바르게 동작함을 보였다. As embedded system becomes more complex, software development becomes more important in the entire design process. Most embedded applications consist of multi-tasks, that are executed in parallel. So, dataflow model that expresses concurrency naturally is preferred than sequential programming language to develop multitask software. For the execution of multitasking codes, operating system is essential to schedule multi-tasks and to deal with the communication between tasks. But, it is needed to execute multitasking code without OS when the target hardware platform cannot execute OS or target platforms are candidates of design space exploration, because it is very costly to port OS for all candidate platforms of DSE. For this reason, we propose the serialized multitasking code generation technique from dataflow specification. In the proposed technique, a task is specified with dataflow model, and generated as a C code. Code generation consists of two steps: First, a block in a task is generated as a separate function. Second, generated functions are scheduled by a multitasking scheduler that is also generated automatically. To make it easy to write customized scheduler manually, the data structure and information of each task are defined. With the preliminary experiment of DivX player, it is confirmed that the generated code from the proposed framework is efficiently and correctly executed on the target system.

멀티 프로세서 시스템-온-칩(MPSoC)을 위한 버스 매트릭스 구조의 빠르고 정확한 성능 예측 기법 (pp.259-260)

김성찬(Sungchan Kim),하순희(Soonhoi Ha) 한국정보과학회 2007 한국정보과학회 학술발표논문집 Vol.34 No.2A

혼선을 고려한 채널 배선 방법

전주식(Chu Shik Jhon),장경선(Kyoung-Son Jhang),하순희(Soonhoi Ha) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.10

VLSI 공정 기술의 발달로 칩 상에서 전선간 간격이 점점 가까와 지고 있다. 그에 따라 구현된 VLSI 회로가 빠르고 정확하게 동작하도록 하기 위해서 레이아웃 설계 과정에서 인접 전선간의 결합 축전량으로 발생하는 혼선을 줄이는 것을 중요한 요인으로 고려하게 되었다. 설계 과정에서 네트 별로 혼선에 대한 상한치가 주어지는 것이 보통이며, 이를 혼선 제약 조건이라고 한다. 이 논문에서는 혼선 제약 조건을 고려한 그리드 채널 배선 문제를 다룬다. 제안된 방법은 트랙 수 최소화를 목적으로 하는 기존의 채널 배선 방법으로 생성된 초기 배선에 대해 수평 선분들을 재배열하여 혼선 제약 조건을 만족하도록 한다. 이 방법은 주어진 트랙 수 내에서 혼선 제약 조건을 만족하는 해가 없는 경우에는 최소의 트랙 수 증가로 혼선 제약 조건을 만족하는 배선을 찾는다. 실험 결과 이 방법은 트랙 재배치 방법보다 효율적임을 관찰할 수 있었다. The inter-wire spacing in a VLSI chip becomes closer as the VLSI fabrication technology rapidly evolves. Accordingly, it becomes important to consider crosstalk caused by the coupling capacitance between adjacent wires in the layout design for the fast and safe VLSI circuits. The upper bounds of the crosstalk for nets, called crosstalk constraint, are usually given in the design specification. This paper deals with the gridded channel routing problem with crosstalk constraints. In this paper, we present a channel routing technique which generates a routing to satisfy crosstalk constraints from an initial routing generated by conventional routers. The proposed technique is based on the repeated rearrangements of horizontal segments in the initial routing. In addition, the proposed technique tries to find a routing to satisfy crosstalk constraints with the minimum increase of the number of tracks in cases where it cannot find a routing to satisfy crosstalk constraints with the given number of tracks. With experiments, we observed that the presented technique is more effective than the track permutation technique.

시스템-온-칩의 하드웨어-소프트웨어 통합 시뮬레이션을 위한 다목적 설계 프레임워크

주영표(Young-Pyo Joo),윤덕용(Dukyoung Yun),김성찬(Sungchan Kim),하순희(Soonhoi Ha) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.9·10

SoC(System-on-Chip)를 설계함에 있어서 칩의 복잡도 증가로 인하여, RTL(Register Transfer Level)에 기반한 기존의 시스템 성능 분석 및 검증 기법 만으로는 점차 짧아지는 ‘시장 적기 출하 (time-to-market)’ 요구에 효율적으로 대응할 수 없게 되었다. 이를 극복하기 위하여 설계 초기 단계부터 지속적으로 시스템을 검증하기 위한 새로운 설계 방법이 요구되었으며, TLM(Transaction Level Modeling) 추상화 수준을 가진 하드웨어-소프트웨어(HW-SW) 통합 시뮬레이션이 이러한 문제를 해결하기 위한 방법으로 널리 연구되고 있다. 그러나 대부분의 HW-SW 통합 시뮬레이터들은 다양한 추상화 수준 중일부만을 지원하고 있으며, 서로 다른 추상화 수준을 지원하는 툴들 간의 연계도 쉽지 않다. 이를 극복하기 위하여 본 논문에서는 HW-SW 통합 시뮬레이션을 위한 다목적 설계 프레임워크를 제안한다. 제안하는 프레임워크는 소프트웨어 응용의 설계를 포함하는 체계적인 SoC 설계 플로우를 제공하며, 각 설계 단계에서 다양한 기법들을 유연하게 적용할 수 있는 동시에, 다양한 HW-SW 통합 시뮬레이터들을 지원한다. 또한 플랫폼을 추상화 수준과 모델링 언어에 독립적으로 설계할 수 있어, 다양한 수준의 시뮬레이션 모델 생성이 가능하다. 본 논문에서는 실험을 통하여, 제안하는 프레임워크가 ARM9 기반의 상용 SoC 플랫폼을 정확하게 모델링 할 수 있는 동시에, MJPEG 예제의 성능을 44%까지 향상시키는 성능 최적화를 수행할 수 있음을 검증하였다. As the complexity of SoC (System-on-Chip) design increases dramatically, traditional system performance analysis and verification methods based on RTL (Register Transfer Level) are no more valid for increasing time-to-market pressure. Therefore a new design methodology is desperately required for system verification in early design stages, and hardware-software (HW-SW) cosimulation at TLM (Transaction Level Modeling) level has been researched widely for solving this problem. However, most of HW-SW cosimulators support few restricted abstraction levels only, which makes it difficult to integrate HW-SW cosimulators with different abstraction levels. To overcome this difficulty, this paper proposes a multipurpose framework for HW-SW cosimulation to provide systematic SoC design flow starting from software application design. It supports various design techniques flexibly for each design step, and various HW-SW cosimulators. Since a platform design is possible independently of abstraction levels and description languages, it allows us to generate simulation models with various abstraction levels. We verified the proposed framework to model a commercial SoC platform based on an ARM9 processor. It was also proved that this framework could be used for the performance optimization of an MJPEG example up to 44% successfully.

모바일 내장형 시스템을 위한 듀얼-포트SDRAM의 성능 평가 및 최적화 (pp.542-546)

양희석(Hoeseok Yang),김성찬(Sungchan Kim),박해우(Hae-woo Park),김진우(Jinwoo Kim),하순희(Soonhoi Ha) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.5

최근 듀얼-프로세서 기반의 모바일 내장형 시스템을 위한 듀얼-포트SDRAM이 발표 되었다. 이는 단일 메모리 칩이 두 프로세서의 로컬 메모리와 공유 메모리 역할을 모두 담당하므로 공유 메모리를 위하여 추가의 SRAM 메모리를 사용하는 기존의 구조에 비해 더 간단한 통신 구조이다. 양 포트로부터의 동시적인 접근에서의 상호 배타성을 보장하기 위하여 모든 공유 메모리 접근에는 특수한 동기화 기법이 수반되어야 하는데 이는 잠재적인 성능 악화의 원인이 된다. 이 논문에서는 이러한 동기화 비용을 고려하여 듀얼-포트SDRAM 구조의 성능을 평가하고, 주 응용의 통신 특성을 고려하여 최적화한 락우선권 기법과 정적복사 기법을 제안한다. 더 나아가, 공유 뱅크를 여러 블록으로 나눔으로써 서로 다른 블록들에 대한 동시적인 접근을 가능케 하여 성능을 개선하도록 한다. 가상 프로토타이핑 환경에서 수행된 실험은 이러한 최적화 기법들이 기본 듀얼-포트SDRAM 구조에 비하여 20-50%의 성능 향상을 가져옴을 보여준다. Recently dual-port SDRAM (DPSDRAM) architecture tailored for dual-processor based mobile embedded systems has been announced where a single memory chip plays the role of the local memories and the shared memory for both processors. In order to maintain memory consistency from simultaneous accesses of both ports, every access to the shared memory should be protected by a synchronization mechanism, which can result in substantial access latency. We propose two optimization techniques by exploiting the communication patterns of target applications: lock-priority scheme and static-copy scheme. Further, by dividing the shared bank into multiple blocks, we allow simultaneous accesses to different blocks thus achieve considerable performance gain. Experiments on a virtual prototyping system show a promising result - we could achieve about 20-50% performance gain compared to the base DPSDRAM architecture.