| '''이론 컴퓨터 과학 {{{#!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=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | 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. 개요
Beowulf cluster클러스터(cluster)는 여러 컴퓨터를 상호 연결하여 한 덩어리로 구성한 시스템이다. 이와 같이 컴퓨터를 묶는 것을 클러스터화 또는 클러스터링이라고 한다. 클러스터화 된 컴퓨터군은 한 대의 컴퓨터를 다루는 것처럼 관리ㆍ운용할 수 있으며, 한 대의 컴퓨터로는 달성할 수 없는 성능이나 가용성 따위를 얻을 수 있다. - 우리말샘
위에 기술된 바와 같이 베오울프 클러스터(Beowulf cluster)는 클러스터의 일종으로, 여러 컴퓨터를 상호 연결하여 한 덩어리로 구성한 시스템이기는 하지만, 가성비를 극대화하기 위해 CPU와 RAM을 한 개의 노드(node)로 단위화해서 네트워크로 연결한 다음 보조기억장치(HARD)와 부팅시퀸스를 가진 메인 컴퓨터가 이러한 여러 노드들을 연산 처리에 총동원하는 형태이다. NASA에서 진행하여 완성한 베오울프 프로젝트(Beowulf project)가 사실상 그 기원이기에 이를 가리키기도 한다. 한편, 베오울프 클러스터가 클러스터 컴퓨터의 전형적인 기준으로 사용되고 있어 슈퍼 컴퓨터 같은 경우에서처럼 이러한 기준에서처럼 클러스터 컴퓨터를 베오울프 클러스터로 여기기도 한다.2. 구성
노드(node)의 마더보드(Motherboard)가 WoL(Wake-on-LAN)를 지원한다면 원격으로 전원을 켜고 끌 수 있다. 이후 POST(Power-on self-test)가 진행되고 이어서 노드의 마더보드가 PXE(Preboot Execution Environment)를 지원한다면 BIOS 수준에서 네트워크를 통한 부팅 개시 절차로 진입하게 된다. 하지만, 여기서부터 리눅스 운영체제와 같은 서버 컴퓨터와 랜(LAN)선으로 연결되어 있어야 비로소 부팅을 완료할 수 있는 OS(운영체제) 데이터를 전송받을 수 있다. 이때에는 보통 인식절차를 위한 DHCP와 부팅에 필요한 자원제공을 위한 FTP 프로토콜을 사용한다.
이러한 베오울프 클러스터는 결과적으로 슈퍼컴퓨터나 워크스테이션급 고속 연산을 수행하는 하드웨어적인 병렬컴퓨터의 구현이겠으나, 고속 연산 수행은 실질적으로 소프트웨어 쪽에서 MPI(Message Passing Interface) 같은 병렬 처리 프로그래밍이 전제되어야 한다. 또한, 노드들은 하드디스크 같은 보조기억장치나 모니터, 키보드 같은 입출력 장치 마저 없는, 그야말로 오직 연산만을 위한 하나의 거대한 마더보드만 한 CPU칩을 의미한다고 할 수 있다.
3. 역사
1995년에 컴퓨터 클러스터의 장점을 취하고 단점을 개선해서 가성비를 극대화하기 위해 NASA에서 진행하여 완성한 베오울프 프로젝트(Beowulf project)가 그 효시이다. 공식 명칭은 The Beowulf parallel workstation project이다.[1] 개발자로는 NASA의 도널드 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): 베오울프 프로젝트 초기에는 노드의 자원을 연산만을 위한 최소한의 수준으로 제한하면서 부팅을 실행해야하는 제약조건을 해결하여야 했다. 원격 부팅 및 원격 전원인가(ON/OFF)는 불가능했으며 고려사항도 아니었다. 3.5인치 플로피 디스크(FD)가 부팅을 위해 장착되어야 했고 이 FD에는 안정적인 부팅을 완료하기 위해 1MB도 안되는 용량으로 아주 심하게 다이어트된 Linux OS가 설계되어 들어갔다. 수동으로 일일이 노드 컴퓨터들의 전원을 인가하면 여러 플로피 디스크들이 읽히는 소리가 장관이다.*2세대(generation): 드디어 2010년을 전후해서 마더보드가 랜카드를 내장하게됨에 따라 WOL(원격 전원ON/OFF)과 PXE(원격 부팅 부트스트랩)를 지원하기 시작했다. 더이상 노드의 마더보드에 연산목적(CPU,RAM)이외의 어떠한 추가 장착도 필요없게 되었다. 그야말로 노드들은 연산만을 위한 클라이언트이자 슬레이브(slave)들로 작동하도록 최적화 될수있게된 것이다.
*3세대 : 무선wifi, 라즈베리 파이나 스마트폰같은 초소형보드 , 5V(dc) 저전력등이 주요 핵심 스펙이 되고있다.
4. 영향
베오울프 클러스터와 같은 컴퓨터 클러스터 기술은 병렬 프로그래밍(parallel programs)을 기반으로 하는데, 이러한 병렬 연산 처리의 병렬 컴퓨팅(parallel computing)의 보급화는 슈퍼컴퓨터의 하드웨어 사양의 주류를 만들어내는 데 영향을 주었고[2] 이러한 병렬 연산 처리(parallel computing)의 일반화는 CPU코어의 병렬 아키텍처(parallel architectures)를 가능하게 하는 데 영감을 주었다고 할 수 있다.5. 핸드쉐이킹 프로토콜
핸드쉐이킹 프로토콜(protocol) 줄여서 핸드쉐이킹(handshaking)은 정보 및 통신쪽에서 데이터를 전송할 때 두 장치 간에 상호 동기신호(同期信號)로 이를 맞추기 위하여 일련의 예약된 정보를 주고받는 것을 가리킨다. 핸드쉐이킹(handshaking)의 어원은 두 사람의 악수(握手)에서 연유한다.5.1. 핸드쉐이킹 프로토콜 예시
5.1.1. 나는 누구입니까?
베어울프 노드 1 : (전원(power)이 인가된후 자신의 고유한 ID(보통 랜카드고유번호인 MAC 주소)로 서버측에 질의한다.) 나는 누구입니까?[3][4]베어울프 노드 2 : (전원 인가)나는 누구입니까?
베어울프 노드 3 : (전원 인가)나는 누구입니까?
베어울프 서버 : (각각의 노드 1,2,3에게 사전에 예약된 MAC 주소에 일대일대응하는 네이밍(naming)[5]을 알려준다.) (노드 1에게)너는 '베타'(beta)이다,(노드 2에게)너는 '브라보'이다,(노드 3에게)너는 '찰리'다
베어울프 노드 1 : (드디어) '베타'라는 계정으로 서버에 접속(login)해 서버측 자원(asset)을 ftp프로토콜을 사용해 가져올수있게된다.
베어울프 노드 2 : '브라보'라는 계정을 사용할수있게된다.
베어울프 노드 3 : '찰리'라는 계정을 사용할수있게된다.
베어울프 서버 : (노드1,2,3의 부팅이 완료되면)계정을 인식하고 연산수행 지시를 내린다.
베어울프 노드 1,2,3 : (연산수행완료후) 결과값을 전송한다.
베어울프 서버 : 노드 1,2,3 의 결과값을 가지고 최종 연산을 결정한다.
6. 관련 문서
[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/[3] \[beowulf project\]DHCP Help Again https://www.beowulf.org/pipermail/beowulf/2002-April/006677.html[4] who am I but a Grendel ,whose mother a witch ,an ogre and a bitch,beautiful I suppose,she captured Beowulf's soul,pathetic father I know,So I attack the village ,loot rape and pillage,father spoils me,yells at then releases,and I am free to burn rape and pillage ,the Norseland village , \[Grendel\] Andy Caldwell , May 7(Thursday), 2015[5] 여기서 네이밍에 부여된 이름은 서버측에 이미 사전에 고유하게 부여된 (클라이언트)계정명의 리스트이다. 이때 서버측에서 MAC 주소에 기반한 DB의 무결성 검사처럼 이러한 맥락(context)에서 DHCP를 실시간으로 처리하기도 한다.