시스템 프로그래밍 - Vector의 Inner Product 함수 분석 및 보완

소개

ㅅㄱㄱ대학교 ㅇㅇㅇ교수님 시스템프로그래밍 과제입니다. (고득점)
- R.Bryant, D.O'Hallaron, Computer Systems: A Programmer's Perspective (2nd Edition) 교재에 나오는 vector의 inner product를 여러가지 방법에 대해 보완해나가는 과정을 직접 프로그래밍하고 분석하는 과제입니다. (책 과제번호 5.15, 5.16, 5.17)

목차

1. 컴파일 결과
2. 실행 결과
3. 문제풀이
4. 참고문헌

본문내용

A. Inner product를 구하기 위해 sum에 벡터의 각 요소를 더하는 연산이 실행된다. 이 때, 덧셈 연산과 곱셈 연산이 꼭 필요하므로 최소한으로 필요한 연산의 수가 2가 된다. 따라서 한 연산을 할 때 CPE값이 1보다 작아질 수 없으므로, inner product의 CPE값은 2보다 작아질 수 없다.
B. 정수의 경우 곱셈과 덧셈에 대해 결합법칙이 성립하므로 컴파일러가 다음과 같이 re-association함으로써 critical path가 변경되고, CPE를 줄일 수 있다.
(a) sum = (((sum + xdata[i]*ydata[i]) + xdata[i+1]*ydata[i+1]) + xdata[i+2]*ydata[i+2]);
(b) sum = sum + (xdata[i]*ydata[i] + xdata[i+1]*ydata[i+1] + xdata[i+2]*ydata[i+2]);
(a)의 경우에는 sum에 값을 더하는 것이 serial로 이루어져서 sum이 갱신되지 않으면 다음 xdata*ydata를 더할 수 없어서 CPE가 줄어들지 않지만, (b)의 경우에는 multiplication을 각각 동시에 진행한 다음 더한 값에 sum을 더함으로써 실질적인 iteration 횟수를 줄이게 된다.
그러나 정수의 경우에는 결합법칙이 성립하지 않기 때문에 컴파일러가 임의로 re-association 할 수 없고, 그에 따라 iteration 횟수가 inner4()와 동일하기 때문에 CPE가 줄어들지 않는다.

<중 략>

A. #5.16-A에서와 같이 sum에 값을 저장할 때 + 연산과 * 연산이 하나씩 꼭 있다. 즉, 기본적으로 수행해야 하는 연산의 수가 2이기 때문에 CPE값이 2보다 작아질 수 없다.
B. IA32의 경우 레지스터의 수가 x86-64보다 적기 때문에 함수에서 사용하는 변수의 수가 많아지면 변수가 레지스터에 저장되지 않고 stack에 저장된다. Stack에 저장되면 데이터를 불러올 때 레지스터에서 불러오는 시간보다 훨씬 긴 시간이 소모된다

참고자료

· R.Bryant, D.O'Hallaron, Computer Systems: A Programmer's Perspective (2nd Edition)