병렬 랜덤 접근 기계
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
병렬 랜덤 접근 기계(PRAM) 모델에서 구현된 FindMax 모듈은 SystemVerilog로 작성되어, 입력 데이터 배열에서 최댓값을 찾는 기능을 수행한다. 이 모듈은 clock, resetN 신호를 입력받고, len개의 8비트 데이터 배열을 입력으로 받아 최댓값을 출력한다. COMPARE, MERGE, DONE의 세 가지 상태를 가지는 유한 상태 기계(FSM)를 통해 동작하며, COMPARE 상태에서 모든 데이터 쌍을 비교하여 최댓값이 아닌 값을 식별하고, MERGE 상태에서 비교 결과를 바탕으로 최댓값을 찾아 출력한 후 DONE 상태로 종료된다.
더 읽어볼만한 페이지
- 병렬 알고리즘 분석 - 암달의 법칙
암달의 법칙은 시스템 자원 개선으로 속도 향상을 얻는 부분의 비율을 고려하여 전체 작업의 이론적인 실행 시간을 계산하고, 이를 통해 전체 작업의 속도 향상 정도를 파악하는 이론이다. - 병렬 알고리즘 분석 - 구스타프슨의 법칙
구스타프슨의 법칙은 병렬 컴퓨팅에서 프로세서 수를 늘릴 때 얻는 속도 향상을 나타내는 법칙으로, 컴퓨팅 자원 증가에 따라 문제 크기도 증가할 수 있다는 점을 고려하여 병렬화 효율성을 재정의한다. - 계산 모형 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다. - 계산 모형 - 양자 회로
양자 회로는 양자 컴퓨팅에서 양자 논리 게이트들을 연결한 회로로, 큐비트의 양자역학적 특성을 활용하여 계산을 수행하며 양자 계산의 핵심 요소로서 연구가 활발히 진행되고 있다.
| 병렬 랜덤 접근 기계 | |
|---|---|
| 기본 정보 | |
 | |
| 설계 패러다임 | 병렬 처리 |
| 시간 복잡도 | O(log n) |
| 자료 구조 | 배열 |
| 관련 주제 | RAM 기계 PRAM 병렬 컴퓨팅 알고리즘 |
2. SystemVerilog 코드
systemverilog
module FindMax #(parameter int len = 8)
(input bit clock, resetN, input bit[7:0] data[len], output bit[7:0] maxNo);
typedef enum bit[1:0] {COMPARE, MERGE, DONE} State;
State state;
bit m[len];
int i, j;
always_ff @(posedge clock, negedge resetN) begin
if (!resetN) begin
for (i = 0; i < len; i++) m[i] <= 0;
state <= COMPARE;
end else begin
case (state)
COMPARE: begin
for (i = 0; i < len; i++) begin
for (j = 0; j < len; j++) begin
if (data[i] < data[j]) m[i] <= 1;
end
end
state <= MERGE;
end
MERGE: begin
for (i = 0; i < len; i++) begin
if (m[i] == 0) maxNo <= data[i];
end
state <= DONE;
end
endcase
end
end
endmodule
2. 1. 모듈 정의
verilogFindMax 모듈은 len개의 8비트 입력 데이터(data) 중 최댓값(maxNo)을 찾아 출력하는 모듈이다. clock, resetN 신호를 입력받으며, len은 파라미터로 설정 가능하다. 기본값은 8이다. FindMax 모듈은 COMPARE, MERGE, DONE의 세 가지 상태(State)를 가진다.
COMPARE 상태에서는 모든 입력 데이터 쌍을 비교하여 data[i]가 data[j]보다 작으면 m[i]를 1로 설정한다. MERGE 상태에서는 m[i]가 0인 data[i]를 찾아 maxNo로 출력한다. 이후 DONE 상태로 전이된다.
2. 2. 상태 정의
PRAM 모델에서 FSM은 세 가지 상태를 갖는다. 먼저, COMPARE 상태에서는 모든 프로세서가 동시에 배열의 모든 원소를 비교한다. 이 과정은 각 원소가 다른 모든 원소보다 큰지 여부를 확인하는 방식으로 진행된다. 다음으로, MERGE 상태에서는 비교 결과를 바탕으로 최댓값을 찾는다. 만약 어떤 원소가 다른 모든 원소보다 크다면, 해당 원소가 최댓값으로 결정된다. 마지막으로, DONE 상태에서는 알고리즘이 종료되고 결과를 출력한다.```SystemVerilog
typedef enum bit[1:0] {COMPARE, MERGE, DONE} State;
2. 3. 변수 선언
코드에서 사용되는 변수들은 다음과 같다.- `len`: 데이터 배열의 길이를 나타내는 파라미터로, 기본값은 8이다.
- `clock`: 클럭 신호이다.
- `resetN`: 리셋 신호 (active low)이다.
- `data`: 8비트 데이터 배열(길이 `len`)이다.
- `maxNo`: `data` 배열 중 최댓값을 저장하는 8비트 출력 변수이다.
- `State`: 유한 상태 기계(FSM)의 상태를 나타내는 열거형 타입이다. `COMPARE`, `MERGE`, `DONE`의 세 가지 상태를 가진다.
- `state`: 현재 상태를 저장하는 변수이다.
- `m`: 각 `data` 요소가 다른 요소보다 작은지 여부를 나타내는 비트 배열(길이 `len`)이다.
- `i`, `j`: 반복문에서 사용되는 정수형 변수이다.
`FindMax` 모듈은 `clock` 신호의 상승 에지(posedge)와 `resetN` 신호의 하강 에지(negedge)에 동기화되어 동작한다. `resetN`이 0이면, `m` 배열의 모든 요소가 0으로 초기화되고, `state`는 `COMPARE` 상태로 설정된다. `resetN`이 1이면, `state` 변수에 따라 동작이 수행된다. `COMPARE` 상태에서는 모든 `data` 요소 쌍을 비교하여 `m` 배열을 업데이트한다.`MERGE` 상태에서는 `m` 배열에서 0인 요소에 해당하는 `data` 값을 `maxNo`에 할당한다.
2. 4. always_ff 블록
`always_ff` 블록은 클럭의 포지티브 에지(posedge) 또는 리셋 신호의 네거티브 에지(negedge)에 동기화되어 동작하는 블록이다. 이 블록은 주로 플립플롭(flip-flop)과 같은 순차 회로(sequential circuit)를 모델링하는 데 사용된다. `FindMax` 모듈에서는 `always_ff` 블록을 사용하여 상태(`state`)와 내부 변수(`m`)의 업데이트, 그리고 최댓값(`maxNo`) 출력을 제어한다.`always_ff` 블록 내부는 크게 리셋 조건(`!resetN`)과 그 외의 경우(else)로 나뉜다.
- 리셋 동작: 리셋 신호(`resetN`)가 활성화되면(즉, `resetN`이 0이 되면), 모든 내부 변수 `m[i]`는 0으로 초기화되고, 상태(`state`)는 `COMPARE`로 설정된다. 이는 `FindMax` 모듈의 동작을 초기화하는 역할을 한다.
- 클럭 동기 동작: 리셋 신호가 비활성화되면(즉, `resetN`이 1이 되면), `always_ff` 블록은 클럭의 포지티브 에지에 동기화되어 동작한다. 현재 상태(`state`)에 따라 다른 동작을 수행한다.
- * `COMPARE` 상태: 모든 데이터 요소를 비교하여 최댓값이 아닌 요소들을 চিহ্নিত한다. 이 과정은 다음과 같이 진행된다.
먼저, 모든 i와 j에 대해 `data[i]`와 `data[j]`를 비교한다. 만약 `data[i]`가 `data[j]`보다 작으면, `m[i]`에 1을 할당한다. 즉, `data[i]`가 최댓값이 아니라는 것을 표시한다. 이중 for 루프를 통해 모든 데이터 요소 쌍을 비교하며, 이를 통해 최댓값이 아닌 요소들을 찾아낸다.
이 비교 과정이 끝나면, `MERGE` 상태로 전이한다.
- * `MERGE` 상태: 비교 결과 배열 m을 기반으로 최댓값을 찾아 `maxNo` 출력에 할당한다.
모든 i (0 ≤ i < len)에 대해 반복하여 `m[i]`가 0이면, `data[i]`를 `maxNo`에 할당한다. 즉, 이전 `COMPARE` 단계에서 다른 어떤 `data[j]`보다 작지 않은 (크거나 같은) `data[i]`가 최댓값으로 선택된다. 이후 상태를 `DONE`으로 변경한다.
- * `DONE` 상태: 최댓값 탐색 완료 후의 상태이다. `MERGE` 상태에서 `m[i]`가 0인 경우, 즉 해당 인덱스의 데이터(`data[i]`)가 최댓값인 경우 `maxNo`에 `data[i]`를 할당한 후 `DONE` 상태로 전이한다.
2. 4. 1. 리셋 동작
wikitext리셋 신호(`resetN`)가 활성화되면(즉, `resetN`이 0이 되면), 모든 내부 변수 `m[i]`는 0으로 초기화되고, 상태(`state`)는 `COMPARE`로 설정된다. 이는 `FindMax` 모듈의 동작을 초기화하는 역할을 한다.
2. 4. 2. COMPARE 상태
COMPARE 상태에서는 모든 데이터 요소를 비교하여 최댓값이 아닌 요소들을 চিহ্নিত한다. 이 과정은 다음과 같이 진행된다.먼저, 모든 i와 j에 대해 `data[i]`와 `data[j]`를 비교한다. 만약 `data[i]`가 `data[j]`보다 작으면, `m[i]`에 1을 할당한다. 즉, `data[i]`가 최댓값이 아니라는 것을 표시한다. 이중 for 루프를 통해 모든 데이터 요소 쌍을 비교하며, 이를 통해 최댓값이 아닌 요소들을 찾아낸다.
```systemverilog
for (i = 0; i < len; i++) begin
for (j = 0; j < len; j++) begin
if (data[i] < data[j]) m[i] <= 1;
end
end
```
이 비교 과정이 끝나면, MERGE 상태로 전이한다.
2. 4. 3. MERGE 상태
wikitextMERGE 상태에서는 비교 결과 배열 m을 기반으로 최댓값을 찾아 maxNo 출력에 할당한다.
- MERGE 상태의 동작:
- * 모든 i (0 ≤ i < len)에 대해 반복:
- ** m[i]가 0이면, data[i]를 maxNo에 할당한다. 즉, 이전 COMPARE 단계에서 다른 어떤 data[j]보다 작지 않은 (크거나 같은) data[i]가 최댓값으로 선택된다.
- * 상태를 DONE으로 변경한다.
이러한 과정을 통해, FindMax 모듈은 MERGE 상태에서 최종적으로 최댓값을 maxNo 출력에 할당하고 동작을 완료한다.
2. 4. 4. DONE 상태
최댓값 탐색 완료 후의 상태이다. MERGE 상태에서 `m[i]`가 0인 경우, 즉 해당 인덱스의 데이터(`data[i]`)가 최댓값인 경우 `maxNo`에 `data[i]`를 할당한 후 DONE 상태로 전이한다.```systemverilog
module FindMax #(parameter int len = 8)
(input bit clock, resetN, input bit[7:0] data[len], output bit[7:0] maxNo);
typedef enum bit[1:0] {COMPARE, MERGE, DONE} State;
State state;
bit m[len];
int i, j;
always_ff @(posedge clock, negedge resetN) begin
if (!resetN) begin
for (i = 0; i < len; i++) m[i] <= 0;
state <= COMPARE;
end else begin
case (state)
COMPARE: begin
for (i = 0; i < len; i++) begin
for (j = 0; j < len; j++) begin
if (data[i] < data[j]) m[i] <= 1;
end
end
state <= MERGE;
end
MERGE: begin
for (i = 0; i < len; i++) begin
if (m[i] == 0) maxNo <= data[i];
end
state <= DONE;
end
endcase
end
end
endmodule
3. 동작 방식
wikitext
FindMax 모듈은 최댓값을 찾기 위해 다음 단계를 거친다.
1. COMPARE: 모든 입력 데이터 쌍 (data[i], data[j])을 비교한다. 만약 data[i]가 data[j]보다 작으면 m[i]를 1로 설정한다. 이 과정을 통해 각 data[i]에 대해 자신보다 큰 data[j]의 개수를 m[i]에 저장한다.
2. MERGE: m[i]가 0인 data[i]를 찾는다. m[i]가 0이라는 것은 data[i]보다 큰 값이 없다는 의미이므로, 이 data[i]가 최댓값(maxNo)이 된다.
3. DONE: 모든 과정이 종료되었음을 나타낸다.
이 모듈은 ''len''개의 입력 데이터 중에서 최댓값을 찾는데, 이때 각 단계는 동기화된 클럭(clock)에 따라 순차적으로 진행된다. 리셋 신호(resetN)가 활성화되면, 모든 m[i]는 0으로 초기화되고, 상태(state)는 COMPARE로 설정된다.
4. 추가 설명
FindMax 모듈은 파라미터 `len`을 사용하여 모듈이 처리할 수 있는 데이터의 길이를 유연하게 조정할 수 있다. `len`의 기본값은 8이다. 이 모듈은 비교(COMPARE), 병합(MERGE), 완료(DONE)의 세 가지 상태를 가지는 유한 상태 기계(FSM)로 구현되었다.
COMPARE 상태에서는 모든 데이터 요소를 서로 비교하여 각 요소가 최댓값인지 여부를 나타내는 비트 배열 `m`을 생성한다. MERGE 상태에서는 `m` 배열에서 0으로 표시된 요소, 즉 다른 어떤 요소보다 작지 않은 요소를 찾아 `maxNo`에 할당한다. 마지막으로 DONE 상태에서는 추가적인 동작을 수행하지 않고 결과를 유지한다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com