|
'''
이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' |
|||||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
<colbgcolor=#aa3366> 이론 | ||||
| 기본 대상 | 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^ 힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
클러스터(cluster)는 여러 컴퓨터를 상호 연결하여 한 덩어리로 구성한 시스템이다. 이와 같이 컴퓨터를 묶는 것을 클러스터화 또는 클러스터링이라고 한다. 클러스터화 된 컴퓨터군은 한 대의 컴퓨터를 다루는 것처럼 관리ㆍ운용할 수 있으며, 한 대의 컴퓨터로는 달성할 수 없는 성능이나 가용성 따위를 얻을 수 있다. - 우리말샘
위에 기술된 바와 같이 베어울프 클러스터(Beowulf cluster)는 클러스터의 일종으로, 여러 컴퓨터를 상호 연결하여 한 덩어리로 구성한 시스템이기는 하지만, 가성비를 극대화하기 위해 CPU와 RAM을 한 개의 노드(node)로 단위화해서 네트워크로 연결한 다음 보조기억장치(HARD)와 부팅시퀸스를 가진 메인 컴퓨터가 이러한 여러 노드들을 연산 처리에 총동원하는 형태이다.
나사(NASA)에서 진행하여 완성한 베오울프 프로젝트(Beowulf project)가 사실상 그 기원이기에 이를 가리키기도 한다. 한편, 베어울프 클러스터가 클러스터 컴퓨터의 전형적인 기준으로 사용되고 있어 슈퍼 컴퓨터 같은 경우에서처럼 이러한 기준에서처럼 클러스터 컴퓨터를 베어울프 클러스터로 여기기도 한다.2. 구성
노드(node)의 마더보드(mother board)가 WOL(wakeup on LAN)를 지원한다면 원격으로 전원을 켜고 끌 수 있다. 이후 파워 온 셀프 테스트(power on self test)가 진행되고 이어서 노드의 마더보드가 PXE(Pre-boot eXecution Environment)를 지원한다면 BIOS 수준에서 네트워크를 통한 부팅 개시 절차로 진입하게 된다. 하지만, 여기서부터 리눅스 운영체제와 같은 서버 컴퓨터와 랜(LAN)선으로 연결되어 있어야 비로소 부팅을 완료할 수 있는 OS(운영체제) 데이터를 전송받을 수 있다. 이때에는 보통 FTP 프로토콜을 사용한다.
이러한 베어울프 클러스터는 결과적으로 슈퍼컴퓨터나 워크스테이션급 고속 연산을 수행하는 하드웨어적인 병렬컴퓨터의 구현이겠으나, 고속 연산 수행은 실질적으로 소프트웨어 쪽에서 MPI(Message Passing Interface) 같은 병렬 처리 프로그래밍이 전제되어야 한다. 또한, 노드들은 하드디스크 같은 보조기억장치나 모니터, 키보드 같은 입출력 장치 마저 없는, 그야말로 오직 연산만을 위한 하나의 거대한 마더보드만 한 CPU칩을 의미한다고 할 수 있다.
3. 역사
1995년에 컴퓨터 클러스터의 장점을 취하고 단점을 개선해서 가성비를 극대화하기 위해 나사(NASA)에서 진행하여 완성한 베오울프 프로젝트(Beowulf project)가 그 효시이다. 공식 명칭은 The Beowulf parallel workstation project이다.[1] 개발자로는 나사의 도널드 J. 베커(Donald J. Becker), 토마스 스털링(Thomas Sterling), 존 E. 도반드(John E. Dorband), 메릴랜드 대학교의 다니엘 사바레세(Daniel Savarese), 휴즈STX코프(Hughes STX Corp)의 우다야 A. 라나와케(Udaya A. Ranawake), 찰스 V. 파커(Charles V. Packer)등이 참여하였다.이 프로젝트의 어원인 베오울프(Beowulf 또는 베어울프)는 북유럽 게르만족의 영웅이자 그를 주인공으로 삼은 고대 서사시의 제목이다.
3.1. 제너레이션
*1세대(generation) : 베오울프 프로젝트(Beowulf project)초기에는 노드의 자원을 연산만을 위한 최소한의 수준으로 제한하면서 부팅을 실행해야하는 제약조건을 해결하여야 했다. 원격 부팅 및 원격 전원인가(ON/OFF)는 불가능했으며 고려사항도 아니었다. 3.5인치 플로피 디스크(FD)가 부팅을 위해 장착되어야 했고 이 FD에는 안정적인 부팅을 완료하기 위해 1MB도 안되는 용량으로 아주 심하게 다이어트된 리눅스OS가 설계되어 들어갔다. 수동으로 일일이 노드 컴퓨터들의 전원을 인가하면 여러 플로피 디스크들이 읽히는 소리가 장관이다.*2세대(generation) : 드디어 2010년을 전후해서 마더보드가 WOL(원격 전원ON/OFF)과 PXE(원격 부팅 부트스트랩)를 지원하기 시작했다. 더이상 노드의 마더보드에 연산목적(CPU,RAM)이외의 어떠한 추가 장착도 필요없게 되었다. 그야말로 노드들은 연산만을 위한 클라이언트이자 슬레이브(slave)들로 작동하도록 최적화 될수있게된 것이다.
4. 영향
베어울프 클러스터와 같은 컴퓨터 클러스터 기술은 병렬 프로그래밍(parallel programs)을 기반으로 하는데, 이러한 병렬 연산 처리의 병렬 컴퓨팅(parallel computing)의 보급화는 슈퍼컴퓨터의 하드웨어 사양의 주류를 만들어내는 데 영향을 주었고[2] 이러한 병렬 연산 처리(parallel computing)의 일반화는 CPU코어의 병렬 아키텍처(parallel architectures)를 가능하게 하는 데 영감을 주었다고 할 수 있다.5. 관련 문서
[1]
BEOWULF: A PARALLEL WORKSTATION FOR SCIENTIFIC COMPUTATION ,Donald J. Becker,Thomas Sterling
https://webhome.phy.duke.edu/~rgb/brahma/Resources/beowulf/papers/ICPP95/icpp95.html
[2]
\[TOP500\]June 2022
https://www.top500.org/lists/top500/2022/06/