병렬 랜덤 접근 기계

병렬 랜덤 접근 기계(parallel random-access machine) 또는 병렬 램(parallel RAM, PRAM)은 컴퓨터 과학에서 공유 메모리 추상 기계이다. 이름에서 알 수 있듯이 PRAM은 RAM(랜덤 접근 기계)에 대한 병렬 컴퓨팅 비유로 사용된다(랜덤 액세스 메모리와 구별됨).[1] 순차 알고리즘 설계자가 알고리즘 성능(예: 시간 복잡도)을 모델링하기 위해 RAM을 사용하는 것과 마찬가지로 PRAM은 병렬 알고리즘 설계자가 병렬 알고리즘 성능(예: 프로세서 수에 따른 시간 복잡도)을 모델링하는 데 사용된다. 일반적으로 가정된 내용도 명시되어 있다). RAM 모델이 주 메모리 대비 캐시 메모리에 대한 액세스 시간과 같은 실질적인 문제를 무시하는 방식과 유사하게 PRAM 모델은 동기화 및 통신과 같은 문제를 무시하지만 문제 크기에 따라 원하는 수의 프로세서를 제공한다. 예를 들어 알고리즘 비용은 두 개의 매개변수 O(시간)과 O(시간 × 프로세서_번호)를 사용하여 추정된다.

예시 코드

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

같이 보기

각주

  1. ↑ Fortune, Steven; Wyllie, James (1978년 5월 1일). 〈Parallelism in random access machines〉. 《Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78》. New York, NY, USA: Association for Computing Machinery. 114–118쪽. doi:10.1145/800133.804339. hdl:1813/7454. ISBN 978-1-4503-7437-8. 

외부 링크