pkg://Parallel-Processing-HOWTO-html.tar.gz:76146/Parallel-Processing-HOWTO-4.html
downloads
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="SGML-Tools 1.0.9">
<TITLE>Linux Parallel Processing HOWTO: 하나의 레지스터위에서의 SIMD(예: MMX 사용)</TITLE>
<LINK HREF="Parallel-Processing-HOWTO-5.html" REL=next>
<LINK HREF="Parallel-Processing-HOWTO-3.html" REL=previous>
<LINK HREF="Parallel-Processing-HOWTO.html#toc4" REL=contents>
</HEAD>
<BODY>
<A HREF="Parallel-Processing-HOWTO-5.html">다음</A>
<A HREF="Parallel-Processing-HOWTO-3.html">이전</A>
<A HREF="Parallel-Processing-HOWTO.html#toc4">차례</A>
<HR>
<H2><A NAME="s4">4. 하나의 레지스터위에서의 SIMD(예: MMX 사용)</A></H2>
<P>
<P>단일 레지스터 내의 SIMD(SWAR)는 새로운 아이디어가 아니다.
<EM>k</EM>-비트 레지스터, 데이터 패스, 그리고 함수 유닛 을 가지는 기계가
있을 때 일반 레지스터 연산들이 <EM>n</EM>개의 <EM>k</EM>/<EM>n</EM>-비트,
정수 필드 값들 위에서 SIMD 병렬 연산들로 수행될 수 있다는 것이
오래전부터 알려져 왔다. 그러나 SWAR 기술들에 의해서 제공되는 2배에서
8배까지의 속도 증가가 메인스트림 컴퓨팅에 대한 관심사가 된 것은 요즘들어
멀티미디어에 대한 강렬한 추세때문이다. 마이크로프로세서들의 1997 버전
대부분은 SWAR에 대한 하드웨어 지원을 담고 있다:
<P>
<UL>
<LI>
<A HREF="http://www.amd.com/html/products/pcd/techdocs/appnotes/20726a.pdf">AMD K6 MMX (MultiMedia eXtensions)</A>
</LI>
<LI>
<A HREF="http://www.cyrix.com:80/process/SUPPORT/isv.htm">Cyrix M2 MMX (MultiMedia eXtensions)</A>
</LI>
<LI>
<A HREF="http://ftp.digital.com/pub/Digital/info/semiconductor/literature/alphahb2.pdf">Digital Alpha MAX (MultimediA eXtensions)</A>
</LI>
<LI>
<A HREF="http://hpcc997.external.hp.com:80/wsg/strategies/pa2go3/pa2go3.html">Hewlett-Packard PA-RISC MAX (Multimedia Acceleration eXtensions)</A>
</LI>
<LI>
<A HREF="http://developer.intel.com/drg/mmx/">Intel Pentium II & Pentium with MMX (MultiMedia eXtensions)</A>
</LI>
<LI>
<A HREF="http://www.microunity.com/www/mediaprc.htm">Microunity Mediaprocessor SIGD (Single Instruction on Groups of Data)</A>
</LI>
<LI>
<A HREF="http://www.mips.com/arch/ISA5/">MIPS Digital Media eXtension (MDMX, pronounced Mad Max)</A>
</LI>
<LI>
<A HREF="http://www.sun.com/sparc/vis/index.html">Sun SPARC V9 VIS (Visual Instruction Set)</A></LI>
</UL>
<P>새로운 마이크로프로세서들에 의해서 제공되는 하드웨어 지원에는 몇가지
결함들이 있고 어떤 필드 크기들에 대해서 어떤 연산들만을 지원하는 것과
같은 단점이 있다. 그러나 많은 SWAR 연산들이 효율적이어야 하는 하드웨어
지원이 필요없다는 것을 기억하는 것이 중요하다. 예를 들어서 비트단위
연산들은 하나의 레지스터를 논리적으로 분할하는 것에 의해서 영향을 받지
않는다.
<P>
<H2><A NAME="ss4.1">4.1 SWAR: 어디에 좋은 것이가(What Is It Good For)?</A>
</H2>
<P>
<P>비록 <EM>모든</EM> 현재 프로세서들이 적어도 어던 SWAR 병렬
기능(parallelism)과 함께 수행하는 것이 가능하다고 하더라도 가장 좋은
SWAR-개선 명령 셋들도 아주 일반적인-목적의 병렬 기능(parallelism)을
지원하지 않는다는 것이 슬픈 사실이다. 사실, 많은 사람들이 Pentium과
"Pentium with MMX technology" 사이의 수행 능력 차이가 우연히도 MMX와
동시에 나타난 더 큰 L1 캐쉬와 같은 것들 때문이라고 생각한다. 그렇다면
SWAR(즉 MMX)는 현실적으로 어디에 좋은 것인가?
<P>
<UL>
<LI>정수들만 있는 것이, 더 적은 것이 더 좋다. 32-비트 값들은 64-비트
MMX 레지스터에 맞아 떨어지지만 8개의 1-바이트 문자들이나 1-비트값들의
체스판 크기(체스판은 가로 세로 8개씩의 칸이 있다. 그래서 64개;
역자주) 개수 전체이더라도 맞아 떨어진다.
Note: 이 글을 쓰고 있는 순간 비록 많은 내용이 없지만 <EM>MMX의
부동-소숫점 버전이 있을</EM> 것이다. Cyrix는 <B>MMFP</B>에 대한 몇가지
설명을 담은 슬라이드들을
<A HREF="ftp://ftp.cyrix.com/developr/mpf97rm.pdf">ftp://ftp.cyrix.com/developr/mpf97rm.pdf</A>에 포스팅해놓았다. 얼른
봐서 MMFP는 두 32-비트 부동-소숫점 숫자들이 64-비트 MMX 레지스터 하나에
팩킹되는 것을 지원할 것이다; 이것을 두개의 MMFP 파이프라인들로 묶으면
클럭 하나당 네개의 단일-정밀도 FLOP를 생산할 것이다.
</LI>
<LI>SIMD, 또는 벡터-스타일 병렬 처리(parallelism). 동일한 연산이 모든
필드들에 동시에 적용된다. 선택된 필드들에 효과를 없애는 방법들(즉, SIMD
enable 마스킹)이 존재하지만 그들은 복잡하고 성능을 저하시킨다.
</LI>
<LI>지역화(localized)되고 정규적인(오히려 팩킹된), 메모리 참조 패턴들.
일반적인 SWAR, 그리고 특별히 MMX, 는 랜덤-순서 접근에 쥐약이다; 벡터
<CODE>x[y]</CODE>(여기서 <CODE>y</CODE>는 인덱스 배열이다)를 모으는 것은 엄청
비싸다.</LI>
</UL>
<P>이들은 심각한 제약점들이지만 이런 타입의 병렬 처리는 많은 병렬
알고리즘들에서 나타나는 것이다 - 멀티미디어 어플리케이션들뿐만이 아니고.
알고리즘의 적절한 타입에 대해서 SWAR는 SMP나 클러스터 병렬 처리보다 훨씬
효율적이다... 그리고 이것은 그것을 사용하는 데 어떤 추가 비용도 들지
않는다.
<P>
<H2><A NAME="ss4.2">4.2 SWAR 프로그래밍에 대한 소개(Introduction To SWAR Programming)</A>
</H2>
<P>
<P>SWAR의 기본 개념(컨셉), 단일 레지스터 안에서의 SIMD, 는 워드-길이
레지스터들 위에서의 연산들이 <EM>n</EM>개의 <EM>k</EM>/<EM>n</EM>-비트
필드 수치들에 대한 SIMD 병렬 연산을 수행함으로써 계산 속도를 높이는 데
사용될 수 있다는 것이다. 그러나 SWAR 기술을 사용하는 것은 다소 어색할 수
있으며 또한 어떤 SWAR 연산들은 실제 대응되는 일련의 순차적인 연산들보다,
그들이 필드 분할을 수행하는 추가의 명령어들을 요구하기 때문에, 더
고 비용이다.
<P>이 관점을 예시하기 위해서 상당히 단순화된, 각 32-비트 레지스터 안에서
4개의 8-비트 필드들을 관리하는, SWAR 메카니즘을 생각해보도록 하자. 두
레지시터들안의 수치들은 다음과 같이 표현될 수 있겠다:
<P>
<HR>
<PRE>
PE3 PE2 PE1 PE0
+-------+-------+-------+-------+
Reg0 | D 7:0 | C 7:0 | B 7:0 | A 7:0 |
+-------+-------+-------+-------+
Reg1 | H 7:0 | G 7:0 | F 7:0 | E 7:0 |
+-------+-------+-------+-------+
</PRE>
<HR>
<P>이것은 단순하게 각 레지스터가 기본적으로 4개의 독립 8-비트 정수 수치들의
벡터로 볼 수 있다는 것을 의미한다. 또는 항목 0 (PE0)를 처리하는 Reg0와
Reg1에 있는 수치들로써 <CODE>A</CODE>와 <CODE>E</CODE>를, 그리고 PE1의
레지스터들에 있는 수치들로써 <CODE>B</CODE>과 <CODE>F</CODE>를, 그리고 계속 이런
식으로 생각할 수 있다.
<P>이 문서의 나머지 부분은 이런 정수 벡터들에 대한 SIMD 병렬 연산을 위한
기본 클래스들과 이들의 함수들이 어떻게 구현될 수 있는 가에 대해서
대략적으로 리뷰할 것이다.
<P>
<H3>다형성 연산(Polymorphic Operations)</H3>
<P>
<P>어떤 SWAR 연산들은, 이 연산이 실제 이런 8-비트 필드들에 병렬로 서로
독립적으로 계산되도록 의도되었다는 사실에 신경쓰지 않고서 일반 32-비트
정수 연산들을 사용해서 쉽게 수행될 수 있다. 우리는 임의의 이런 SWAR
연산들을 <EM>다형성(polymorphic)</EM>이라고 부른다. 왜냐면 이 기능이
필드 타입들(크기들)에 의해서 영향을 받지 않기 때문이다.
<P>임의의 필드가 영이 아닌가를 테스트하는 것은 다형성이다. 그리고 모든
비트단위 논리 연산들도 그렇다. 예를 들어서 일반 비트단위 and 논리
연산(C의 <CODE>&</CODE> 연산자)은 비트단위로 수행하고 그 필드 크기가
얼마나 되는지에 신경쓰지 않는다. 위 레지스터들의 단순한 비트단위 and
연산 결과는 다음과 같은 결과를 만들어 낸다:
<P>
<HR>
<PRE>
PE3 PE2 PE1 PE0
+---------+---------+---------+---------+
Reg2 | D&H 7:0 | C&G 7:0 | B&F 7:0 | A&E 7:0 |
+---------+---------+---------+---------+
</PRE>
<HR>
<P>비트단위 and 연산은 항상 연산대상 비트 <EM>k</EM> 수치들에 의해서만
영향을 받는 결과 비트 <EM>k</EM>의 수치를 가지기 때문에 어떤 필드
크기라도 동일한 단일 명령에 의해서 지원받는다.
<P>
<H3>분할된 연산(Partitioned Operations)</H3>
<P>
<P>불행하게도 많은 중요한 SWAR 연산들이 다형성이 아니다. 더하기, 빼기,
곱하기, 나누기 등과 같은 사칙연산들은 모두 필드들간의
자리올림(carry)/빌려옴(borrow) 상호작용을 할 수밖에 없다. 우리는 이런
SWAR 연산들을 <EM>분할된(partitioned)</EM> 것이라고 부른다. 왜냐면 각
연산이 반드시 연산대상들을 효율적으로 분할해야 하고 필드들 간의
상호작용을 막아야 하기 때문이다. 그러나 이런 효과를 얻는 데 사용될 수
있는 세가지 서로 다른 방법들이 존재한다.
<P>
<H3>분할된 명령어(Partitioned Instructions)</H3>
<P>
<P>분할된 연산들을 구현하는 가장 명백한 접근법은 필드들 간의 carry/borrow
논리를 자르는 "분할된 병렬 명령어"에 대한 하드웨어 지원을 제공하는
것이다. 이런 접근은 최고의 성능을 내지만 프로세서의 명령 집합을 변경해야
하고 일반적으로 필드 크기에 많은 제한들이 있다(예, 8-비트 필드들이
지원될 수 있지만 12-비트 필드들은 그렇지 못한 경우).
<P>AMD/Cyrix/Intel MMX, Digital MAX, HP MAX, 그리고 Sun VIS는 모두 분할
명령들의 제한된 버전들을 구현한 것들이다. 불행하게도 이런 서로 다른 명령
셋 확장들은 중요한 다른 제약들을 가지기 때문에 그들간에 알고리즘들이
서로 포팅될 수 없게 만든다. 예를 들어서 다음과 같은 분할된 연산의
샘플링을 생각해보자:
<P>
<HR>
<PRE>
Instruction AMD/Cyrix/Intel MMX DEC MAX HP MAX Sun VIS
+---------------------+---------------------+---------+--------+---------+
| Absolute Difference | | 8 | | 8 |
+---------------------+---------------------+---------+--------+---------+
| Merge Maximum | | 8, 16 | | |
+---------------------+---------------------+---------+--------+---------+
| Compare | 8, 16, 32 | | | 16, 32 |
+---------------------+---------------------+---------+--------+---------+
| Multiply | 16 | | | 8x16 |
+---------------------+---------------------+---------+--------+---------+
| Add | 8, 16, 32 | | 16 | 16, 32 |
+---------------------+---------------------+---------+--------+---------+
</PRE>
<HR>
<P>이 테이블에서 숫자들은 각 연산이 지원되는 필드 크기들을 비트 단위로
나타낸 것이다. 비록 이 테이블이 좀 더 훌륭한 것들을 포함한 많은 명령들을
생략한 것이기는 하지만 많은 차이가 있다는 것은 분명한 사실이다.
이의 직접적인 결과는 고-수준 언어들(High-Level Languages; HLLs)가 실제로
프로그래밍 모델로써 아주 적합한 것은 아니다라는 것과 포팅이 일반적으로
아주 나쁘다는 것이다.
<P>
<H3>교정 코드를 가지는 분할되지 않은 연산(Unpartitioned Operations With Correction Code)</H3>
<P>
<P>분할 명령어들을 사용해서 분할 연산들을 구현하는 것은 분명히 효율적일 수
있지만 필요한 분할 연산이 하드웨어에 의해서 지원되지 않으면 어떻게 할
것인가? 해답은 필드간 carry/borrow을 가진 연산들을 일반 명령어들을
사용해서 수행하고 원하지 않는 필드 상호작용을 교정하는 것이다.
<P>이것은 순전히 소프트웨어로 접근하는 것이고 교정작업은 오버헤드를
일으키지만 완전히 일반적인 필드 분할로 잘 작동한다. 이런 접근법은
분할 명령에 대한 하드웨어 지원의 갭들을 채우는 데 사용될 수 있거나
아니면 하드웨어 지원을 전혀 하지 않는 타겟 기계들에 대해서 완전한 기능을
제공하는 데 사용될 수 있다는 점에서 또한 완전히 일반적이다. 사실 C와
같은 언어로 코드 시퀀스들을 표현함으로써 이런 접근법은 SWAR 프로그램들이
완전히 포팅 가능한 것으로 만든다.
<P>그렇다면 다음과 같은 질문이 바로 생긴다: 비분할 연산들을 교정 코드로
SWAR 분할 연산들을 시물레이션하는 것이 정확히 얼마나 비효율적인가? 글쎄
이것은 확실히 $64k 문제이다... 하지만 많은 연산들이 예상하는
것만큼 어려운 것은 아니다.
<P>일반적인 32-비트 연산들을 사용해서 네개의 성분을 가지는 8-비트 정수
벡터들 두개를 더하는 것, <CODE>x</CODE>+<CODE>y</CODE>을 생각해보자.
<P>일반적인 32-비트 덧셈은 실제로 정확한 결과를 만들지만 8-비트 필드들 중
하나라도 다음 필드로 캐리(자리 올림)를 만든다면 정확한 결과를 만들어내지
못한다. 그래서 우리의 목적은 단순하게 그런 캐리가 일어나지 않도록
보장하는 것이다. 두개의 <EM>k</EM>-비트 필드들을 더하는 것은 많아야
<EM>k</EM>+1 비트 결과를 만들어 내기 때문에 우리는 각 필드의 msb(most
significant bit)를 단순히 "마스킹 제거(masking out)"함으로써 어떤 캐리도
발생하지 않도록 보장할 수 있다. 이것은 <CODE>0x7f7f7f7f</CODE>로 각
피연산자를 비트단위 and(bitwise anding)하고 나서 일반 32-비트 더하기를
수행함으로써 이루어진다.
<P>
<HR>
<PRE>
t = ((x & 0x7f7f7f7f) + (y & 0x7f7f7f7f));
</PRE>
<HR>
<P>이 결과는 정확하다... 각 필드의 msb를 제외하고 말이다. 각 필드에 대해서
교정값을 계산해보자. 이것은, <CODE>x</CODE>와 <CODE>y</CODE>의 msb들을 <CODE>t</CODE>에
대해서 계산된 7-비트 캐리 결과에 두 개의 1-비트 분할된 덧셈을 하는
문제에 지나지 않는다. 다행스럽게도 1-비트 분할 덧셈은 일반 exclusive or 연산으로 구현되어 있다. 그래서 그 결과는 다음과 같다:
<P>
<HR>
<PRE>
(t ^ ((x ^ y) & 0x80808080))
</PRE>
<HR>
<P>좋다, 글쎄, 이것은 그렇게 단순한 것이 아닐 수 있다. 결국 4개의 덧셈을
위해서 6번 연산을 수행한다. 그러나 연산이 횟수는 필드가 몇개인가에 따라
다르지 않다는 것을 주목하자. 그래서 좀 더 많은 필드들이 있으면 우리는
속도 향상을 얻을 수 있다. 사실 필드들이 단일 연산(정수 벡터)으로
로드되고 저장되었기 때문에, 우리는 어떤 식으로든 단순하게 속도 향상할 수
있으며, 레지스터 가용성은 개선될 수 있고, 동적 코드 스케줄링
종속성이 더 적다(부분 워드 참조를 피할 수 있기 때문에).
<P>
<H3>필드 수치 제어(Controlling Field Values)</H3>
<P>
<P>부분 연산 구현에 대한 다른 두가지 접근법 둘 다 레지스터들에 대한 공간
활용을 최대화하려고 하는 반면에, 대신 필드 값들을 제어해서 내부-필드
캐리/빌림 이벤트들이 절대 일어나지 않도록 하는 것이 좀 더 계산 측면에선
효율적이다. 예를 들어서 우리가 더해진 모든 필드 값들이 어떤 필드
오버플로우도 일어나지 않는다는 것을 안다면 부분 더하기 연산은 일반적인
더하기 명령을 사용해서 구현될 수 있다; 사실 이런 제한이 주어지면
일반적인 더하기 연산이 다형성(역자주: 필드 크기에 독립이다)인 것처럼
보이고 교정 코드 없이 어떤 필드 크기들에도 사용 가능하다. 그래서 어떻게
필드 값들이 캐리/빌림 이벤트를 발생시키지 않도록 보장할 수 있는가가
관건이 된다.
<P>이런 특성을 보장하는 한 가지 방법은 필드 값들의 범위를 제한할 수 있는
부분화된 명령들을 구현하는 것이다. Digital MAX 벡터 minimum과 maximum
명령들은 내부-필드 캐리/빌림을 피하기 위해서 필드 값들을 클립핑(역자주:
자름)하는 하드웨어적인 지원이다.
<P>그러나 우리가 필드 값들의 범위를 효과적으로 제한할 수 없는 부분화된
명령들을 가지지 못한다고 가정하자... 갑싸게 캐리/빌림 이벤트들이 인접
필드들 사이에 간섭하지 않는다고 보장하도록 할 수 있는 충분한 조건이
있는가? 이의 해답은 사칙연산 특성의 분석에 있다. 두 <EM>k</EM>-비트
숫자들을 더하는 것은 많아야 <EM>k</EM>+1 비트로 된 숫자를 생성한다;
그래서 <EM>k</EM>+1 비트는 일반 명령들을 사용함에도 불구하고 그런 연산을
안전하게 담을 수 있다.
<P>그래서 우리의 이전 예제안에서 8-비트 필드들이 이제는 1-비트의 "캐리/빌림
완충기(spacers)"를 가지는 7-비트 필드들이라고 가정하자:
<P>
<HR>
<PRE>
PE3 PE2 PE1 PE0
+----+-------+----+-------+----+-------+----+-------+
Reg0 | D' | D 6:0 | C' | C 6:0 | B' | B 6:0 | A' | A 6:0 |
+----+-------+----+-------+----+-------+----+-------+
</PRE>
<HR>
<P>7-비트 덧셈의 벡터는 다음과 같이 수행된다. 어떤 부분 연산을 시작하기
이전에 모든 캐리 완충 비트들(<CODE>A'</CODE>, <CODE>B'</CODE>, <CODE>C'</CODE>,
그리고 <CODE>D'</CODE>)가 0이라는 값을 갖는다고 가정하자. 단순하게 일반 덧셈
연산을 수행함으로써 모든 필드들은 정확한 7-비트 값들을 얻는다; 그러나
어떤 완충 비트 값들은 이제 1이 될 수 있다. 우리는 이것을
전통적인 연산인 완충 비트들에 대한 마스크-제거를 한번 더 수행함으로써
교정할 수 있다. 우리의 7-비트 정수 벡터 덧셈, <CODE>x</CODE>+<CODE>y</CODE>은
그래서 다음과 같다:
<P>
<HR>
<PRE>
((x + y) & 0x7f7f7f7f)
</PRE>
<HR>
<P>이것은 네개의 덧셈을 두 명령어로 줄인 것이다. 그래서 이것은 좋은 속도
향상을 분명히 가져올 것이다.
<P>주의 깊은 독자(sharp reader)는 완충 비트들을 0으로 설정하는 것은 빼기
연산에서 작동하지 않는다는 것을 눈치챘을 것이다. 그러나 그 교정 방법이
아주 단순하다. <CODE>x</CODE>-<CODE>y</CODE>를 계산하기 위해서 우리는
<CODE>x</CODE>에 있는 완충 비트들은 모두 1이고 <CODE>y</CODE>에 있는 완충
비트들은 모두 0이라는 초기 조건을 확실하게 한다. 가장 나쁜 경우에 우리는
다음과 같은 것을 얻을 것이다:
<P>
<HR>
<PRE>
(((x | 0x80808080) - y) & 0x7f7f7f7f)
</PRE>
<HR>
<P>그러나 추가의 비트별 or 연산은 종종, <CODE>x</CODE>의 값을 생성하는 연산이
<CODE>& 0x7f7f7f7f</CODE> 대신에 <CODE>| 0x80808080</CODE>을 마지막
스텝으로써 사용한다는 것을 확실하게 함으로써, 최적화될 수 있다.
<P>어떤 방법이 SWAR 부분화된 연산들에 대해서 사용되어야 할 것인가? 그 답은
단순하게도 "가장 빠른 속도(향상)을 내는 것이면 무엇이든 된다"는 것이다.
흥미롭게도 사용하기 위한 이상적인 방법은 동일한 기계위에서 동작하는
동일한 프로그램 내에서(도) 서로 다른 필드 크기들에 대해서 서로 다를 수
있다.
<P>
<H3>통신과 타입 변환 연산(Communication & Type Conversion Operations)</H3>
<P>
<P>비록, 이미지 픽셀들에 대한 많은 연산들을 포함해서, 어떤 병렬 계산은 한
벡터의 <EM>i</EM>번째 값은 피연산자 벡터들의 <EM>i</EM>번째 위치에
나타나는 값들만의 함수이라는 속성을 갖고 있지만, 이것은 일반적으로 그런
경우가 아니다. 예를 들어서 부드럽게 하기(smoothing)와 같은 픽셀
연산들조차 인접 픽셀들을 피연산자들로 요구하고 FFT들과 같은 변환들도 좀
더 복잡한(덜 지역화된) 통신 패턴들을 요구한다.
<P>SWAR를 위한, 부분화되지 않은 쉬프트 연산들을 사용한, 1-차원 가장 근접한
이웃 통신을 효율적으로 구현하는 것은 어려운 일이 아니다. 예를 들어서,
<CODE>PE</CODE><EM>i</EM>로부터 <CODE>PE</CODE>(<EM>i</EM>+1)로 값을 이동하기
위해서 단순한 쉬프트 연산으로도 충분하다. 필드들이 8-비트의 길이를
가진다면 다음과 같이 사용할 것이다:
<P>
<HR>
<PRE>
(x << 8)
</PRE>
<HR>
<P>그러나 이것은 항상 그렇게 단순하지 않다. 예를 들어서
<CODE>PE</CODE><EM>i</EM>로부터 <CODE>PE</CODE>(<EM>i</EM>-1)로 값을 이동하려면,
단순한 쉬프트 연산으로도 충분하다. 그러나 C 언어는 오른쪽 쉬프트가 부호
비트를 보존하는지 않하는지를 지정하지 않고 어떤 기계들은 부호 붙은
오른쪽 쉬프트만을 지원한다. 그래서 일반적인 경우 우리는 반드시
명시적으로, 잠재적인 복사된(replicated) 부호 비트들을 0으로 만들어야
한다:
<P>
<HR>
<PRE>
((x >> 8) & 0x00ffffff)
</PRE>
<HR>
<P>"wrap-around 커넥션들"을 더하는 것도 또한 부분화되지 않은 쉬프트를
사용해서 상당히 효율적이다. 예를 들어서 <CODE>PE</CODE><EM>i</EM>로부터 값을
<CODE>PE</CODE>(<EM>i</EM>+1)로 wraparound를 이용해서 옮기려면:
<P>
<HR>
<PRE>
((x << 8) | ((x >> 24) & 0x000000ff))
</PRE>
<HR>
<P>실질적인 문제는 좀 더 일반적인 통신 패턴이 반드시 구현되어야 한느 경우에
발생한다. 단지 HP MAX 명령어 집합만이 단일 명령으로 필드들의 임의
재배치를 지원한다. 이것은 <CODE>Permute</CODE>라고 불린다. 이
<CODE>Permute</CODE> 명령은 실제로 이름이 잘못 지어졌다; 이것은 필드들의
임의의 permutation
<BLOCKQUOTE>역자주: 순열이라고 번역하지만 수학에서는 일정
개수의 객체들의 자리 이동을 말한다</BLOCKQUOTE>
만 수행하는 것이 아니라
반복(repetition)도 허용한다. 간단히 말해서 이것은 임의의 <CODE>x[y]</CODE>
연산을 수행한다.
<P>불행하게도 <CODE>x[y]</CODE>는 그런 명령없이 구현하기가 아주 어렵다. 코드
시퀀스는 일반적으로 길면서도 비효율적이다; 사실 이것은 순차적인
코드이다. 이것은 아주 실망스러운 것이다. MasPar MP1/MP2와 Thinking
Machines CM1/CM2/CM200
SIMD 슈퍼컴퓨터에서의 <CODE>x[y]</CODE>의 상대적으로 높은 연산 속도는 이런
기계들의 성능이 좋았던 주요 이유들 중의 하나이었다. 그러나
<CODE>x[y]</CODE>는 항상 가장 근접한 이웃 통신보다도, 심지어 그런
슈퍼컴퓨터들에서조차, 더 느리기 때문에 많은 알고리즘들이 <CODE>x[y]</CODE>
연산들에 대한 수요를 최소화하기 위해서 고안되어 왔었다. 간단하게 말해서
하드웨어 지원없이 이것은 <CODE>x[y]</CODE>가 합법적이지 않은 것처럼 또는
적어도 싼 것이 아닌것처럼 SWAR 알고리즘들을 개발하는 것이 가장 좋을
것이다.
<P>
<H3>순환 연산(Recurrence Operations) (축소, 스캔 등)</H3>
<P>
<P>순환이란 계산되는 값들간의 외면상 순차적인 관계가 있는 계산을 말한다.
그러나 이런 순환이 결합적인 연산들을 포함한다면 세개의 구조화된 병렬
알고리즘을 사용하여 그 계산을 재코딩하는 것이 가능할 수 있다.
<P>병렬화가 가능한 순환(recurrence)의 대부분의 일반적인 타입은 아마도 결합
축소(associative reduction)으로 알려진 클래스일 것이다. 예를 들어서 어떤
벡터 값들의 덧셈을 계산하기 위해서 다음과 같은 완전히 순차적인 C 코드를
작성하는 것이 일반적이다:
<P>
<HR>
<PRE>
t = 0;
for (i=0; i<MAX; ++i) t += x[i];
</PRE>
<HR>
<P>그러나, 이런 덧셈의 순서는 다수 별로 중요하지 않다. 부동 소숫점과
극한(saturation) 수학은 덧셈의 순서가 바뀌면 다른 답들을 낼 수 있지만
일반적인 wrap-around 정수 덧셈들은 덧셈의 순서에 관계없이 동일한
결과들을 낼 것이다. 그래서 우리는 이런 시퀀스를, 첫번째 두 값들 쌍들을
더하고, 그다음에 이런 부분합들을 더하고 이런식으로 단일 마지막 덧셈이
나올 때까지 계속하는, 세개의-구조화된 병렬 덧셈으로 재작성할 수 있다.
네개의 8-비트 값들의 벡터에 대해서 두 덧셈 단계들이 필요하다; 첫번째
단계는 두개의 8-비트 덧셈을 수행하고, 그다음 두개의 16-비트 결과
필드들을 생성한다(각각은 9-비트 결과를 담고 있다):
<P>
<HR>
<PRE>
t = ((x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff));
</PRE>
<HR>
<P>두번째 스텝은 이런 두개의 9-비트 값들을 16-비트 필드들안에서, 단일
10-비트 결과를 만들기 위해, 더한다:
<P>
<HR>
<PRE>
((t + (t >> 16)) & 0x000003ff)
</PRE>
<HR>
<P>실제, 두번째 스텝은 두개의 16-비트 필드 덧셈들을 수행한다... 그러나 머리
16-비트 덧셈은 의미가 없다. 이것이 바로 왜 결과가 단일 10-비트 결과 값에
대해서 마스킹되는가에 대한 이유이다.
<P>"병렬 접두어(parallel prefix)" 연산으로 알려진 스캔은 다소 효율적으로
구현하기가 더 어렵다. 이것은 왜냐면, 축소(reduction)과 다르게, 스캔이
부분적인(partitioned) 결과를 내기 때문이다. 이런 이유로 스캔은 아주
명백한, 부분적인 연산들의 시퀀스를 사용해서 구현될 수 있다.
<P>
<H2><A NAME="ss4.3">4.3 리눅스에서의 MMX SWAR</A>
</H2>
<P>
<P>리눅스이 경우 IA32 프로세서들이 우리의 주요 관심사이다. AMD, Cyrix,
그리고 Intel 모두 동일한 MMX 명령어들을 구현한다고 하는 것은 굿뉴스이다.
그러나 MMX 성능은 서로 다르다; 예를 들어서 K6는 MMX 파이프라인을 단지
하나만 가진다 - (이에 반해서)Pentium with MMX는 두개를 가진다. Intel이
아직도 이런 멍청한 MMX 광고를 계속하고 있다는 것이 유일한 배드뉴스이다.
;-)
<P>SWAR를 위하여 MMX를 사용하는 데는 실제 다음과 같은 세가지 접근법이 있다:
<P>
<OL>
<LI>MMX 라이브러리 루틴들을 사용하는 것. 특별히 Intel은 몇가지 "성능
라이브러리들을(performance libraries)",
<A HREF="http://developer.intel.com/drg/tools/ad.htm">http://developer.intel.com/drg/tools/ad.htm</A> 개발했다. 이것은 일반
멀티미디어 작업들에 대해서 손으로-최적화된 다양한 루틴들을 제공한다.
적은 노력으로 많은 비-멀티미디어 알고리즘들이 대부분의 컴퓨터-집중
포션들의 일부가 이런 라이브러리 루틴들을 하나 또는 그이상 사용해서
구현될수 있도록 재작업될 수 있다. 이런 라이브러리들은 현재 리눅스에
대해서 사용불가능이지만 포팅 가능할 수 있다.
</LI>
<LI>MMX 명령어들을 직접 사용하는 것. 이것은 다소 두가지 점들에 의해서
복잡하다. 첫번째 문제는 MMX가 프로세서에서 사용가능하지 않을 수 있어서
대체 구현물이 반드시 제공되어야 할수도 있다는 것이다. 두번째 문제는
리눅스에서 일반적으로 사용되는 IA32 어셈블러가 현재 MMX 명령어들을
이해하지 못한다는 것이다.
</LI>
<LI>적절한 MMX 명령어들을 직접 생성할 수 있는 고-수준 언어나 모듈
컴파일러(module compiler)를 사용하는 것. 그런 툴들은 현재 개발 중에
있지만 어떤 것도 아직 리눅스에서 완전한 기능을 가진 것이 없다. 예를
들어서 퍼듀 대학교 (
<A HREF="http://dynamo.ecn.purdue.edu/~hankd/SWAR/">http://dynamo.ecn.purdue.edu/~hankd/SWAR/</A>)에서 우리는
현재 명시적으로 병렬 C 방언으로 작성된 함수들을 취해서 C 함수들로 가능한
SWAR 모듈들을 생성할 컴파일러를 개발하고 있지만, 아직 MMX를 포함해서
SWAR 지원이 가능한 것이면 무엇이든 사용한다. 첫번째 프로토타입 모듈
컴파일러는 1996년 가을에 만들어졌다. 그러나 이 기술을 사용가능한
상태까지 만드는 것은 처음에 예상한 것보다 더 오래 걸리고 있다.</LI>
</OL>
<P>요약하면 MMX SWAR는 여전히 사용하기에 어렵다. 그러나 여분의 노력을 조금
더하면 위에서 주어진 두번째 접근법은 지금도 사용될 수 있다. 다음은 그
기본이다:
<P>
<OL>
<LI>프로세서가 MMX를 지원하지 않으면 MMX를 쓸 수 없다. 다음 GCC
코드는 MMX가 여러분의 프로세서에서 지원되는지 안되는지를 테스트하는 데
사용될 수 있다. 지원안되면 0이 리턴되고 지원되면 0이 아닌 값이 리턴된다.
<HR>
<PRE>
inline extern
int mmx_init(void)
{
int mmx_available;
__asm__ __volatile__ (
/* Get CPU version information */
"movl $1, %%eax\n\t"
"cpuid\n\t"
"andl $0x800000, %%edx\n\t"
"movl %%edx, %0"
: "=q" (mmx_available)
: /* no input */
);
return mmx_available;
}
</PRE>
<HR>
</LI>
<LI>MMX 레지스터는 기본적으로 GCC가 <CODE>unsigned long long</CODE>라고
부르는 것 중 하나를 갖고 있다. 그래서 이런 타입의 메모리-기반 변수들은
여러분의 MMX 모듈들과 그들을 호출하는 C 프로그램들간의 통신 메카니즘이
된다. 또는 MMX 데이터를 임의의 64-비트 정렬된 데이터 스트럭쳐로
선언할수도 있다 (여러분의 데이터 타입을 <CODE>unsigned long long</CODE>
필드를 가지는 <CODE>union</CODE>의 타입으로 선언함으로써 64-비트
정렬이 되도록 하는 것이 편리하다).
</LI>
<LI>MMX가 사용가능이라면 여러분은, 각 명령을 인코드하는 <CODE>.byte</CODE>
어셈블리 지시어를 사용한 여러분의 MMX 코드를 작성할 수 있다. 예를 들어서
MMX 명령어 <CODE>PADDB MM0,MM1</CODE>는 다음과 같이 GCC 인-라인 어셈블리
코드로 인코딩될 수 있다:
<HR>
<PRE>
__asm__ __volatile__ (".byte 0x0f, 0xfc, 0xc1\n\t");
</PRE>
<HR>
MMX는 부동 소숫점 연산들에 대해서 사용되는 하드웨어와 동일한 것들을
사용한다는 것을 기억하자. 그래서 MMX 코드와 서로 섞인 코드는 부동 소숫점
연산들을 호출해서는 안된다. 부동 소숫점 스택도 또한 MMX 코드를 실행하기
전에 비워져야 한다; 부동 소숫점 스택은 일반적으로 부동 소숫점을 사용하지
않는 C 함수의 시작점에서 비워진다.
</LI>
<LI>다음과 같이 코딩될 수 있는 것처럼, <CODE>EMMS</CODE> 명령을
실행함으로써, MMX 코드를 종료하자:
<HR>
<PRE>
__asm__ __volatile__ (".byte 0x0f, 0x77\n\t");
</PRE>
<HR>
</LI>
</OL>
<P>위의 것이 아주 이상하고 조잡하게 보인다면 그렇다. 그러나 MMX는 여전히 꽤
젊다... 이 문서의 나중 버전은 MMX SWAR를 프로그램하는 좀 더 나은
방법들을 제공할 것이다.
<P>
<HR>
<A HREF="Parallel-Processing-HOWTO-5.html">다음</A>
<A HREF="Parallel-Processing-HOWTO-3.html">이전</A>
<A HREF="Parallel-Processing-HOWTO.html#toc4">차례</A>
</BODY>
</HTML>
