Projects‎ > ‎

HW2: Radix Sort (2진수, 2 processes)

- Fork/Pipe, select 포함
- Buket 크기, 전송 블럭 크기
- Memory Utilization, Number of File access
- Report 가이드 (예 실습 환경)

목표.

1. 주어진 초기 코드를 수정하여 2개의 프로세스로 병렬화하여 Radix Sort를 수행한다.

수정해야할 내용.

1. Fork 함수를 사용하여 2개의 프로세스를 생성한다.
2. Pipe를 사용하여 2개의 프로세스간의 통신을 수행한다.
3. select 함수를 사용하여, Blocking I/O 상황을 피한다.

성능 최적화를 위해 수정해야할 내용.

1. Fork에 의해서 생성된 프로세스를 A와 B라고 가정한다.
2. 프로세스 A와 프로세스 B 가 동시에 데이터를 읽어 정렬을 수행할 수 있어야 한다.
3. 프로세스 A와 프로세스 B는 서로간의 양방향 통신을 해야 한다.
4. 각 프로세스가 파일에서 데이터를 읽을 때, 한번에 메모리에 적재할 수 있는 버퍼의 크기를 조절하여 최적의 값을 결정해야 한다.
5. 각 프로세스에서 Radix 정렬의 중간 상태를 저장하는 Buket의 크기를 조절하여 최적의 값을 결정해야 한다.

메모리 사용율을 위한 고려사항

1. Radix 정렬의 중간 상태를 저장하는 Buket에 데이터가 균등하게 들어갈 확률이 낮다.
2. 한쪽으로 편중 될 경우, Buket의 내용을 비우기 위해서 파일에 써야 한다.
3. 이러한 경우, 총 메모리 할당량에 비해서 실제 메모리 사용률이 1/n버킷 수준으로 매우 낮아진다.
4. 이를 해결하기 위해서는 기본 Buket의 단위크기를 작게 하고, 
    편중되는  Buket의 메모리를 점점 크게 할당하는 동적 할당 방식을 사용하여
    실제 메모리 사용률을 높여야 한다.

파일 I/O를 줄이기 위한 고려사항

1. 파일 읽기 횟수와 파일 쓰기 횟수를 줄이는 것이 목표이다.
2. 파일의 읽기/쓰기는 Disk Access를 유발하며, 일반적으로 Disk Access는 Memory Access 속도보다 매우 늦다.
    따라서, 파일 I/O가 많이 발생하면, 프로세스의 성능이 낮아질 수 있다.
3. 파일 읽기 횟수를 줄이기 위해서는 읽기 버퍼의 크기를 늘려, 전체적으로 읽는 횟수를 줄일 수 있다.
4. 파일 쓰기 횟수를 줄이기 위해서는 중간 상태를 저장하는 Radix의 각 버킷의 크기가 늘려, 전체적으로 스기 횟수를 줄일 수 있다.
5. 3과 4는 메모리가 충분히 크다면, 모두 메모리에 적재하여 해결할 수 도 있다.
    하지만 제한된 메모리 크기에서 최적의 성능을 내기 위한 버퍼와 버킷의 크기를 결정해야 한다.

제약사항

1. 프로세스당 메모리 총 사용량: 500MB
    계산 방법.
    a. 본 과제에서 메모리 사용량에서 일반 변수들의 크기는 제외한다.
    b. 메모리 사용량 = 읽기 버퍼 크기 + 각 버킷의 총 크기 

제출해야하는 내용.

1. 별도의 서식을 통해서 보고서를 작성한다.
2. 2개의 프로세스를 사용하여 Radix 정렬을 수행하는 방법.
3. 메모리 사용율을 높이기 위한 방안
4. 파일 I/O를 줄이기 위한 방안
5. 제한된 메모리양 때문에 발생하는 3과 4의 충돌이 무엇인가?
6. 5를 위해서 해결한 내용.
7. <3, 4, 5>에서 최적 값을 찾기 위해 측정한 데이터(그래프)
    두가지 변수:  읽기 버퍼의 크기, 각 버킷의 크기
    측정할 결과:  정렬 시간, 파일 읽기 횟수, 파일 쓰기 횟수,  ( 전체 프로그램 종료시 횟수 )
                        메모리 사용량( 버킷을 파일에 비울때마다 측정 )
    a. 읽기 버퍼의 크기의 증가에 따른 성능의 차이
    b. 각 버킷의 크기의 증가에 따른 성능의 차이
    c. 버킷의 동적 할당에 따른 성능의 차이

힌트

1. 2개의 프로세스를 사용하여 Radix 정렬 수행 아이디어
    파일의 내용을 분할하여 프로세스 A와 프로세스 B가 읽는 영역을 나눈다.
    참고할 함수 : fseek
    - 중간파일 저장할 시 주의할 것.
2. 동적 버킷 할당 아이디어
    연결 리스트 자료구조를 사용하는 방법을 사용한다.
3. 시간 측정 방법
    clock 함수를 사용한다.
    clock_t before = clock();
    clock_t after = clock();
    double 시간 측정 = ( after - before ) / CLOCK_PER_SEC;
4. 메모리 사용량 측정 방법
    BUFFER_LENGTH : 읽기 버퍼의 크기
    READED_BUF_SZ : 읽은 데이터의 크기
    <n>BUKET_LENGTH : 개별 버킷의 크기
    <n>BUKET_SZ : 개별 버킷을 사용한 크기
    a. 메모리 총 할당량 = BUFFER_LENGTH + <0>BUKET_LENGTH + <1>BUKET_LENGTH ...
    b. 메모리 사용량(백분율) = ( READED_BUF_SZ + <0>BUKET_SZ + <1>BUKET_SZ ... ) / 메모리 총 할당량 * 100

Comments