GPU를 이용한 소수 생성기

Rust로 소수를 생성하는 코드 분석 및 설명

안녕하세요! 이번 블로그 글에서는 Rust 프로그래밍 언어를 사용하여 소수를 생성하는 코드를 분석하고, 그 구조와 동작 원리를 자세히 설명하겠습니다. 이 코드는 WGPU 라이브러리를 활용해 GPU에서 소수 계산을 시도하려는 의도를 가지고 있지만, 실제로는 CPU에서 소수를 계산하는 방식을 채택하고 있습니다. 코드의 주요 구성 요소와 각 부분의 역할을 하나씩 살펴보겠습니다.

---

1. 코드 개요

이 코드는 Rust로 작성되었으며, 소수를 효율적으로 계산하기 위해 다음과 같은 주요 구성 요소로 이루어져 있습니다:

• PrimeData 구조체: 소수 여부를 저장하는 데이터 구조.
• ComputeContext 구조체: WGPU 관련 리소스를 관리하며 GPU 계산을 준비.
• compute_primes_cpu 함수: CPU에서 소수를 계산하는 함수.
• compute_primes 함수: 소수를 블록 단위로 나누어 계산.
• main 함수: 프로그램의 진입점으로 전체 계산 과정을 실행.

코드는 GPU를 활용하려는 의도를 보이지만, 현재 구현에서는 CPU에서 계산이 이루어지고 있음을 주목해야 합니다. 이제 각 부분을 자세히 살펴보겠습니다.

---

2. PrimeData 구조체

#[derive(Clone, Copy, Pod, Zeroable)]
#[repr(C)]
struct PrimeData {
    is_prime: u32,
}

• 역할: PrimeData는 특정 숫자가 소수인지 여부를 나타내는 간단한 구조체입니다.
• is_prime 필드: u32 타입으로, 1은 소수를, 0은 소수가 아님을 나타냅니다.
• 특징:
  • #[repr(C)]: C 언어와의 메모리 호환성을 보장합니다.
  • Pod와 Zeroable: bytemuck 라이브러리에서 제공하는 트레이트로, 안전한 메모리 조작을 지원합니다.

이 구조체는 소수 계산 결과를 저장하거나 GPU로 전달할 데이터를 준비하는 데 사용될 수 있는 기반을 제공합니다.

---

3. ComputeContext 구조체

struct ComputeContext {
    device: Device,
    queue: Queue,
    shader: ShaderModule,
    pipeline: ComputePipeline,
    bind_group_layout: BindGroupLayout,
}

• 역할: WGPU의 주요 리소스를 관리하는 구조체로, GPU 계산을 위한 환경을 설정합니다.
• 필드:
  • device: GPU 장치를 나타냅니다.
  • queue: GPU 명령 큐로, 작업을 제출합니다.
  • shader: 계산 셰이더 모듈입니다.
  • pipeline: 계산 파이프라인으로, 셰이더 실행 방식을 정의합니다.
  • bind_group_layout: 바인드 그룹의 레이아웃을 정의합니다.

3.1. new 메서드

async fn new() -> Self {
    let instance = wgpu::Instance::default();
    let adapter = instance
        .request_adapter(&wgpu::RequestAdapterOptions {
            power_preference: wgpu::PowerPreference::HighPerformance,
            force_fallback_adapter: false,
            compatible_surface: None,
        })
        .await
        .expect("GPU 어댑터를 찾을 수 없습니다");

    let (device, queue) = adapter
        .request_device(
            &wgpu::DeviceDescriptor {
                label: None,
                required_features: wgpu::Features::empty(),
                required_limits: wgpu::Limits::default(),
                memory_hints: wgpu::MemoryHints::default(),
            },
            None,
        )
        .await
        .expect("GPU 장치를 생성할 수 없습니다");

    let shader = device.create_shader_module(include_wgsl!("shader.wgsl"));

    let bind_group_layout = device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor { ... });
    let pipeline_layout = device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor { ... });
    let pipeline = device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor { ... });

    Self {
        device,
        queue,
        shader,
        pipeline,
        bind_group_layout,
    }
}

• 기능: WGPU 환경을 초기화합니다.
• 주요 단계:
  1. Instance와 Adapter를 생성하여 GPU를 선택.
  2. Device와 Queue를 요청하여 GPU 리소스를 준비.
  3. shader.wgsl 파일에서 셰이더를 로드.
  4. 바인드 그룹 레이아웃과 계산 파이프라인을 설정.
• 주의점: 셰이더는 로드되지만, 현재 코드에서는 실제로 사용되지 않습니다.

---

4. compute_primes_cpu 함수

fn compute_primes_cpu(limit: u32) -> Vec<u32> {
    let mut is_prime = vec![true; limit as usize];
    if limit > 0 { is_prime[0] = false; }
    if limit > 1 { is_prime[1] = false; }

    let sqrt_limit = (limit as f64).sqrt() as usize + 1;

    for i in 2..sqrt_limit {
        if is_prime[i] {
            let mut j = i * i;
            while j < limit as usize {
                is_prime[j] = false;
                j += i;
            }
        }
    }

    let mut primes = Vec::new();
    for i in 0..limit as usize {
        if is_prime[i] {
            primes.push(i as u32);
        }
    }

    primes
}

• 기능: 에라토스테네스의 체 알고리즘을 사용해 CPU에서 소수를 계산합니다.
• 동작 과정:
  1. is_prime 벡터를 true로 초기화.
  2. 0과 1을 소수가 아닌 것으로 표시.
  3. 2부터 sqrt(limit)까지 반복하며 소수의 배수를 제거.
  4. is_prime이 true인 숫자를 primes 벡터에 추가.
• 결과: 지정된 limit까지의 소수 목록을 반환.

---

5. compute_primes 함수

fn compute_primes(&self, limit: u32) -> Vec<u32> {
    const BLOCK_SIZE: u32 = 200_000;
    let num_blocks = (limit + BLOCK_SIZE - 1) / BLOCK_SIZE;
    let mut all_primes = Vec::new();

    let small_primes = Self::compute_primes_cpu(BLOCK_SIZE);
    all_primes.extend_from_slice(&small_primes);

    for block in 1..num_blocks {
        let start = block * BLOCK_SIZE;
        let end = std::cmp::min(start + BLOCK_SIZE, limit);
        let block_size = end - start;

        let mut is_prime = vec![PrimeData { is_prime: 1 }; block_size as usize];

        for &prime in &small_primes {
            if prime * prime > end { break; }
            let mut start_multiple = ((start + prime - 1) / prime) * prime;
            if start_multiple < prime * prime { start_multiple = prime * prime; }
            if start_multiple < end {
                let first_idx = (start_multiple - start) as usize;
                let mut idx = first_idx;
                while idx < block_size as usize {
                    is_prime[idx].is_prime = 0;
                    idx += prime as usize;
                }
            }
        }

        for i in 0..block_size as usize {
            if is_prime[i].is_prime == 1 {
                all_primes.push(start + i as u32);
            }
        }
    }

    all_primes
}

• 기능: 소수를 블록 단위로 나누어 계산합니다.
• 주요 특징:
  • BLOCK_SIZE는 200,000으로 설정되며, WGPU 워크그룹 제한을 고려한 값입니다.
  • 첫 번째 블록은 CPU에서 계산(compute_primes_cpu)하여 작은 소수를 확보.
  • 이후 블록은 작은 소수를 이용해 배수를 제거하며 소수를 계산.
• 동작 과정:
  1. 범위를 BLOCK_SIZE 단위로 분할.
  2. 각 블록에서 소수의 배수를 제거.
  3. 남은 숫자 중 소수를 all_primes에 추가.
• 주의점: GPU를 사용하려는 의도와 달리, 현재는 CPU에서 계산이 이루어집니다.

---

6. main 함수

fn main() {
    let context = block_on(ComputeContext::new());
    let limit = 2_200_000_000;
    let primes = context.compute_primes(limit);
    let count = std::cmp::min(100_000_000, primes.len());
    for i in 0..count {
        println!("{}", primes[i]);
    }
    println!("총 {}개의 소수를 찾았습니다.", count);
}

• 기능: 프로그램의 진입점으로, 소수 계산을 실행하고 결과를 출력합니다.
• 주요 단계:
  1. ComputeContext를 초기화.
  2. limit을 2.2억으로 설정해 약 1억 개의 소수를 목표.
  3. compute_primes로 소수를 계산.
  4. 최대 1억 개의 소수를 출력.

---

7. 코드의 한계와 개선점

• GPU 미활용: WGPU 환경을 설정했으나, 실제 계산은 CPU에서 수행됩니다. GPU 병렬 처리를 구현하려면 WGSL 셰이더와 컴퓨트 파이프라인을 활용해야 합니다.
• 메모리 효율성: 큰 limit에 대해 is_prime 벡터가 많은 메모리를 사용합니다. 메모리 최적화가 필요할 수 있습니다.
• 성능 향상: GPU를 사용하면 대규모 소수 계산의 속도를 크게 개선할 수 있습니다.

---

8. 결론

이 코드는 Rust와 WGPU를 활용해 소수를 계산하려는 흥미로운 시도를 보여줍니다. 현재는 CPU에서 동작하지만, GPU를 활용한 병렬 계산으로 확장하면 더 높은 성능을 기대할 수 있습니다. 이 코드를 기반으로 GPU 기반 소수 계산을 구현해보는 것은 Rust 개발자들에게 훌륭한 도전 과제가 될 것입니다. 다음 글에서는 실제 GPU 계산 구현을 다뤄볼 수 있기를 기대합니다!

 

※ 타이틀 이미지 출처: 위키백과

---

1억개-소수생성소스.zip

3.0 kB