프로그램은 실행파일 내의 각 명령어를 수행함으로써 전력을 소비한다. 소비 전력은 복잡도와 비례하기 때문에 프로그램의 복잡도를 측정함으로써 예측될 수 있다. 일반적으로 소프트웨어의 복잡도는 마이크로프로세서시뮬레이터를 사용하여 측정한다. 그러나 시뮬레이터를 사용한 복잡도 측정방법은 하드웨어를 트랜지스터 레벨과 같은 낮은 레벨에서 모델링하기 때문에 수행시간이 오래 걸리고, 단순히 정량적 측정치만을 제공한다. 본 논문에서는 소프트웨어의 최상위 레벨인 프로그램의 소스코드를 분석하고, 복잡도 매트릭을 생성하여 프로그램 전체에 대한 복잡도를 수식화하여 표현하는 방법을 제안한다. 또한 복잡도 매트릭을 함수 단위로 생성함으로써 연산이 집중되는 모듈에 대한 세분화된 정보를 제공할 수 있다. 제안한 알고리즘의 성능분석은 게이트 레벨 마이크로프로세서 시뮬레이터인 SimpleScalar와의 비교를 통해서 수행하였다. 분석을 위해 사용된 소프트웨어는 최신 비디오코덱인 H.264/AVC에서 사용되는 $4{\times}4$ 정수변환, 화면 내 예측, 화면 간 예측 모듈이다. 각각의 소프트웨어에 대하여 정량적으로 측정된 성능 분석을 위하여 입력된 각 모듈에 대한 실행 명령어의 수를 비교하였으며, 정확도는 SimpleScalar를 통하여 측정된 시뮬레이션 결과 대비 약 11.6%, 9.6%, 3.5%의 오차를 보였다.
프로그램은 실행파일 내의 각 명령어를 수행함으로써 전력을 소비한다. 소비 전력은 복잡도와 비례하기 때문에 프로그램의 복잡도를 측정함으로써 예측될 수 있다. 일반적으로 소프트웨어의 복잡도는 마이크로프로세서 시뮬레이터를 사용하여 측정한다. 그러나 시뮬레이터를 사용한 복잡도 측정방법은 하드웨어를 트랜지스터 레벨과 같은 낮은 레벨에서 모델링하기 때문에 수행시간이 오래 걸리고, 단순히 정량적 측정치만을 제공한다. 본 논문에서는 소프트웨어의 최상위 레벨인 프로그램의 소스코드를 분석하고, 복잡도 매트릭을 생성하여 프로그램 전체에 대한 복잡도를 수식화하여 표현하는 방법을 제안한다. 또한 복잡도 매트릭을 함수 단위로 생성함으로써 연산이 집중되는 모듈에 대한 세분화된 정보를 제공할 수 있다. 제안한 알고리즘의 성능분석은 게이트 레벨 마이크로프로세서 시뮬레이터인 SimpleScalar와의 비교를 통해서 수행하였다. 분석을 위해 사용된 소프트웨어는 최신 비디오코덱인 H.264/AVC에서 사용되는 $4{\times}4$ 정수변환, 화면 내 예측, 화면 간 예측 모듈이다. 각각의 소프트웨어에 대하여 정량적으로 측정된 성능 분석을 위하여 입력된 각 모듈에 대한 실행 명령어의 수를 비교하였으며, 정확도는 SimpleScalar를 통하여 측정된 시뮬레이션 결과 대비 약 11.6%, 9.6%, 3.5%의 오차를 보였다.
A program consumes energy by executing its instructions. The amount of cosumed power is mainly proportional to algorithm complexity and it can be calculated by using complexity information. Generally, the complexity of a S/W is estimated by the microprocessor simulator. But, the simulation takes lon...
A program consumes energy by executing its instructions. The amount of cosumed power is mainly proportional to algorithm complexity and it can be calculated by using complexity information. Generally, the complexity of a S/W is estimated by the microprocessor simulator. But, the simulation takes long time why the simulator is a software modeled the hardware and it only provides the information about computational complexity quantitatively. In this paper, we propose a complexity estimation method of analysis of S/W on source code level and produce the complexity metric mathematically. The function-wise complexity metrics give the detailed information about the calculation-concentrated location in function. The performance of the proposed method is compared with the result of the gate-level microprocessor simulator 'SimpleScalar'. The used softwares for performance test are $4{\times}4$ integer transform, intra-prediction and motion estimation in the latest video codec, H.264/AVC. The number of executed instructions are used to estimate quantitatively and it appears about 11.6%, 9.6% and 3.5% of error respectively in contradistinction to the result of SimpleScalar.
A program consumes energy by executing its instructions. The amount of cosumed power is mainly proportional to algorithm complexity and it can be calculated by using complexity information. Generally, the complexity of a S/W is estimated by the microprocessor simulator. But, the simulation takes long time why the simulator is a software modeled the hardware and it only provides the information about computational complexity quantitatively. In this paper, we propose a complexity estimation method of analysis of S/W on source code level and produce the complexity metric mathematically. The function-wise complexity metrics give the detailed information about the calculation-concentrated location in function. The performance of the proposed method is compared with the result of the gate-level microprocessor simulator 'SimpleScalar'. The used softwares for performance test are $4{\times}4$ integer transform, intra-prediction and motion estimation in the latest video codec, H.264/AVC. The number of executed instructions are used to estimate quantitatively and it appears about 11.6%, 9.6% and 3.5% of error respectively in contradistinction to the result of SimpleScalar.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
이러한 실행명령어의 수는 프로그램의 알고리즘 레벨 분석을 통해 계산될 수 있다. 본 논문에서 제안하는 방법은 소프트웨어의 소비전력 측정을 위하여 알고리즘 레벨에서 소프트웨어의 복잡도를 예측하는 것이다.
이를 입력으로 분석하여 프로그램의 복잡도 매트릭을 생성한다. 본 논문에서는 ARM 명령어 아키텍쳐를 바탕으로 하여 구현 및 실험을 수행하였다. C/Assembly 혼합 코드를 파일로 저장하기 위해서 ARM gcc 크로스 컴파일러를 사용할 경우 다음의 옵션을 사용하여 컴파일하면 된다.
이는 어셈블리 명령어를 실행시키는 것과 동일하기 때문에 어셈블리 코드를 분석함으로써 프로세서가 개발된 소프트웨어를 동작시키기 위해서 얼마나 많은 명령어를 실행시키는지를 알 수 있다. 본 논문에서는 C/Assembly 혼합 코드를 분석할 수 있는 프로그램을 작성하여 실험하였다. 이는 코드 내에 정해진 몇몇 규칙들을 찾아내어 파일을 분석하는 방법이므로, 기존의 시뮬레이터나 프로파일러와는 비교할 수 없을 정도로 빠른 분석이 가능하다.
본 논문에서는 프로그램의 최적화 과정에 반드시 필요한 복잡도 분석을 위하여 알고리즘 레벨 복잡도 분석 방법을 제안하였다. 제안한 알고리즘은 C/Assembly 혼합 코드를 분석하여 각각의 명령어 블톡, 순환문, 분기 문에 대하여 B, N, P를 사용한 복잡도 매트릭을 생성함으로써 각 모듈별 복잡도를 쉽게 알 수 있도록 하였다.
가설 설정
앞서 설명한 소스코드 분석방법을 사용하여 그림 13 의 예와 같은 매트릭을 생성할 수 있다. 이 매트릭의 각각의 명령어 블록에 포함되는 명령어의 종류와 실행 횟수는 입력된 C/Assembly 혼합 코드의 분석을 통해 정확하게 측정됐다고 가정하자. 이때 그림 13의 프로그램이 실행하는 명령어의 수를 얻기 위해서 Ni, N2, 日의 값을 알아야 한다.
제안 방법
이는 분기가 발생할 확률에 따라서 특정 명령어들이 수행되거나 그렇지 않을 수 있음을 의미한다. 따라서 분기문을 기준으로 명령어 블록이 나뉘어져야 하며, 제안하는 알고리즘 레벨 복잡도 분석 방법에서는 1번째 분기분에 대하여 R을 사용하여 표현한다. 다음 그림 11은 분기문에 대한 C/Assembly 혼합 코드이며, 그림 12는 분기문의 단순화된 어셈블리 구조에 대하여 제안한 알고리즘을 통해 생성된 복잡도 매트릭의 예이다.
본 논문에서 제안하는 소프트웨어의 분석을 위한 알고리즘 레벨의 복잡도 측정 방법은 기존의 시뮬레이터와 달리 소프트웨어의 소스 코드 분석을 통하여 함수별 복잡도 매트릭을 구성함으로써, 소프트웨어의 각 기능 모듈별 복잡도를 파악할 수 있는 방법이다. 제안한 방법을 통해서 프로그램의 세분화된 복잡도와 실행 명령어의 수를 예측할 수 있다.
본 논문에서 제안하는 알고리즘 레벨 복잡도 측정 방법으로 생성되는 매트릭은 상세한 수식을 통하여 각 모듈의 복잡도를 설명한다. 그러나 B, N, P를 통하여 표현되기 때문에 각 순환문의 순환횟수와 분기문의 조건에 대한 확률은 제공되지 않는다.
본 논문에서 제안한 방법의 성능을 검증하기 위하여 복잡도 분석을 위한 소프트웨어의 구현을 통하여 각 명령어 블록에 대한 분석 결과와 복잡도 매트릭을 파일로 저장하도록 하였다. 저장된 명령어 블록은 각 명령어 블록에서 실행되는 모든 명령어의 수와 명령어의 종류별 실행횟수를 포함한다.
본 논문에서 제안한 알고리즘 레벨 복잡도 측정 방법은 C/Assembly 혼합 코드의 분석을 통하여 복잡도 매트릭을 생성하는 것이다. 개발된 소프트웨어가 마이크로프로세서 상에서 실행될 때, 프로세서는 컴파일된 결과로 생성된 기계어 시퀀스를 정해진 규칙에 의해 하나씩 실행시킨다.
본 논문에서는 제안하는 알고리즘 레벨 복잡도 측정 방법은 소스 코드의 컴파일 과정에서 얻어지는 C와 어셈블리어가 혼합된 코드를 분석하여 복잡도 매트릭을 생성한다. 그림 1은 제안하는 알고리즘의 전체적인 구조를 보여준다.
분류된 함수 내에서 순차적으로 수행되는 명령어들을 하나의 블록으로 묶고, 각각의 순환문과 분기 문을 분석한다. 즉, 프로그램 전체로부터 각 모듈의 하위 단계로의 분석을 수행하여 복잡도 매트릭을 생성한다.
264/AVC의 화면 내 예측 모듈에는 예측 방향별로 0~8까지 총 9개의 예측모드가 존재한다. 이에 따라 cif 영상을 사용하여 각 모드에 대한 분기조건별 확률을 구하여 해당 모듈의 복잡도 매트릭에 적용하였으며, 다른 크기의 영상에도 이와 동일한 확률을 적용하였다. 그 결과 각 크기별 영상에 대하여 SimpleScalar 대비 평균 약 9.
제안하였다. 제안한 알고리즘은 C/Assembly 혼합 코드를 분석하여 각각의 명령어 블톡, 순환문, 분기 문에 대하여 B, N, P를 사용한 복잡도 매트릭을 생성함으로써 각 모듈별 복잡도를 쉽게 알 수 있도록 하였다.
대상 데이터
즉, 동일한 프로그램을 입력으로 하여 각각의 프로그램에서 실행되는 명령어의 실행 횟수를 비교함으로써 제안한 알고리즘 레벨 복잡도 측정의 정확도가 비교될 수 있다. 실험을 위하여 사용된 프로그램은 최신 비디오 코덱인 H.264/AVC에서압축 성능에 중요한 비중을 차지하는 4x4 정수변환, 화면 내 예측, 화면 간 예측 모듈이다. 입력 영상의 크기에 따른 비교를 위하여 qcif(176xl44), cif(352x288), NTSC(720><486), PAL(720x576) 영상을 사용하였다.
264/AVC에서압축 성능에 중요한 비중을 차지하는 4x4 정수변환, 화면 내 예측, 화면 간 예측 모듈이다. 입력 영상의 크기에 따른 비교를 위하여 qcif(176xl44), cif(352x288), NTSC(720><486), PAL(720x576) 영상을 사용하였다. 다음 그림 15는 4" 정수변환에 대한 알고리즘 레벨 복잡도 측정 결과와 SimpleScalar를 통해 측정된 실행명령어의 수를 비교한 것이다.
데이터처리
본 논문에서 제안한 알고리즘 레벨 복잡도 측정 결과의 정확도를 측정하기 위해서 II장에서 설명한 시뮬레이터인 SimpleScalar를 사용하여 측정한 프로그램의 총실행 명령어의 수와 제안한 알고리즘을 통해 예측된 총실행 명령어의 수를 비교하였다. 즉, 동일한 프로그램을 입력으로 하여 각각의 프로그램에서 실행되는 명령어의 실행 횟수를 비교함으로써 제안한 알고리즘 레벨 복잡도 측정의 정확도가 비교될 수 있다.
제안한 알고리즘에 대한 검증을 위하여 최신 비디오 코덱인 H.264/AVC의 4x4 정수변환, 화면 내 예측 부호화기, 화면 간 예측 모듈을 입력으로 하여 동일한 입력에 대한 SknpleScalar의 시뮬레이션 결과를 통해 측정된 실행 명령어 수를 비교하였다. 그 결과, 각각의 툴에 대하여 11.
성능/효과
이에 따라 cif 영상을 사용하여 각 모드에 대한 분기조건별 확률을 구하여 해당 모듈의 복잡도 매트릭에 적용하였으며, 다른 크기의 영상에도 이와 동일한 확률을 적용하였다. 그 결과 각 크기별 영상에 대하여 SimpleScalar 대비 평균 약 9.6%의 오차를 보였다.
264/AVC의 4x4 정수변환, 화면 내 예측 부호화기, 화면 간 예측 모듈을 입력으로 하여 동일한 입력에 대한 SknpleScalar의 시뮬레이션 결과를 통해 측정된 실행 명령어 수를 비교하였다. 그 결과, 각각의 툴에 대하여 11.6%, 9.6%, 3.5%의 오차를 확인하였다. 이를 통하여 실제 하드웨어를 모델링하여 실행간 측정을 하는 기존의 시뮬레이터들과는 달리, 소스코드의 분석을 통해서 비교적 정확하게 복잡도를 측정할 수 있음을 증명하였다.
그림 14와 같이 각 명령어 블록에서 수행되는 명령어들의 총합과 명령어 별 수행횟수를 포함하여 순차적으로 저장되며, 각 함수에 해당하는 복잡도 매트릭을 표시한다. 따라서 해당 매트릭에 각 명령어 블록에 포함되는 명령어의 수와 순환횟수 N, 조건 분기 확률 P를 각각 대입함으로써 각 모듈별로 실행되는 명령어의 수와 순환문의 순환횟수 등을 통해 함수 전체에서 실행되는 명령어의 수와 연산이 집중되는 문맥을 알 수 있다.
실험은 각 크기별 영상 한 장에 대하여 수행되었다. 실험에 사용된 영상들에 대하여 Sir頤leScalar와 제안한 알고리즘간의 실행명령어 수에 대한 오차의 평균은 약 11.6%로 측정되었다.
위의 세 가지 실험결과를 통하여 제안한 방법을 통한 복잡도 측정 결과가 입력되는 영상이 커짐에 따라서 시뮬레이터로 측정한 결과와 유사한 비율로 증가함을 알 수 있다. 이는 알고리즘 레벨에서의 복잡도 측정 방법을 사용하여 프로그램을 실행시키지 않고도 실제 시뮬레이션 결과에 근접하게 추정할 수 있음을 의미한다.
5%의 오차를 확인하였다. 이를 통하여 실제 하드웨어를 모델링하여 실행간 측정을 하는 기존의 시뮬레이터들과는 달리, 소스코드의 분석을 통해서 비교적 정확하게 복잡도를 측정할 수 있음을 증명하였다.
명령어의 수를 비교하였다. 즉, 동일한 프로그램을 입력으로 하여 각각의 프로그램에서 실행되는 명령어의 실행 횟수를 비교함으로써 제안한 알고리즘 레벨 복잡도 측정의 정확도가 비교될 수 있다. 실험을 위하여 사용된 프로그램은 최신 비디오 코덱인 H.
후속연구
그러나 이러한 시뮬레이터들은 속도가 매우 느리고, 단순히 프로그램의 수행 간에 실행되는 명령어를 분석하는 것이며, 알고리즘의 분석이라고 할 수 없다. 만일 알고리즘의 분석을 통하여 복잡도가 특히 높은 모듈이나 문맥의 위치를 제공할 수 있다면 최적화 과정을 효과적으로 수행하는데 도움을 줄 수 있을 것이다. 하지만 기존의 시뮬레이터를 통해서 제공되는 정보들은 소프트웨어 개발자에게 어떤 모듈 또는 문맥에서 연산이 집중되는지를 알려줄 수 없다.
참고문헌 (9)
Coleman D. Bagwell, Emil Jovanov, Jeffery H. Kulick, "A Dynamic Power Profiling of Embedded Computer Systems" IEEE System Theory, 2002. Proceedings of the Thirty-Fourth Southeastern Symposium, pp. 15-19, Huntsville, Alabama, March 2002.
Chun-Hao Hsu, Jian Jhen Chen, Shiao-Li Tsao, "Evaluation and modeling of power consumption of a heterogeneous dual-core processor", IEEE Transactions on Volume 24, Issue 7, Computer-Aided Design of Integrated Circuits and Systems, pp. 1030 - 1041, Hsinchu, Taiwan, July 2005.
Yu Hu, Qing Li, C.-C. Jay Kuo, "Run-time Modeling and Estimation of Multimedia System Power Consumption", 11th IEEE International Conference, Embedded and Real-Time Computing Systems and Applications, pp.353-356, 17-19, Hong Kong, China, Aug. 2005.
D. Burger, T. Austin, "The simplescalar tool set version 2.0", Technical Report 1342, Computer Sciences Department, University of Wisconsin, Madison, WI, June 1997.
Toshinori SATO, Yukio OOTAGURO, Masato NAGAMATSU, Haruyuki TAGO, "Evaluation of Architecture-level Power Estimation for CMOS RISC Processors", Low Power Electronics, IEEE Symposium, pp. 44 - 45, San Jose, CA, 9-11 Oct. 1995.
Vivek Tiwari, Sharad Malik, Andrew Wolfe, "Power analysis of embedded software: a first step towards software power minimization", IEEE Trans. Very Large Scale Integration (VLSI) Systems, Vol. 2, no. 4, pp. 437-445, December 1994.
Vivek Tiwari, Sharad Malik, Andrew Wolfe, "Instruction level power analysis and optimization of software", IEEE VLSI Design, 1996. Proceedings., Ninth International Conference, pp. :326 - 328, Bangalore, India, Jan. 1996.
Chi-ying Tsui; Marculescu, R.; Marculescu, D.; Pedram, M., "Improving the efficiency of power simulators by input vector compaction", 33rd IEEE Design Automation Conference, pp. 165-168, Las Vegas, NV, 3-7 June 1996.
Diana Marculescu, Radu Marculescu, Massoud Pedram, "Stochastic Sequential Machine Synthesis Targeting Constrained Sequence Generation", the 33rd annual Design Automation Conference, pp. 696-701, Las Vegas, Nevada, United States, January, 1996.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.