'공부'에 해당되는 글 89건

  1. 2011.08.24 중간언어
  2. 2011.08.24 LR 구문 분석
  3. 2011.08.22 LL 구문 분석
  4. 2011.08.22 구문 분석 (syntax analysis)
  5. 2011.08.20 context-free grammar
  6. 2011.08.20 regular language
  7. 2011.08.20 formal language
  8. 2011.08.19 MIPS 요약
  9. 2011.08.18 Link layer and LANs 1
  10. 2011.08.17 코어의 수와 성능
공부/컴파일러2011. 8. 24. 20:48


중간언어는 단계가 세분화된 컴파일러의 각 모듈들을 연결시켜준다.
컴파일러를 기능적으로 독립적인 여러 모듈들로 구성하는 것이 가능해 졌다.
중간 코드를 이용한 최적화가 기계 코드에서의 최적화보다 효율적이다.
인터프리터를 사용해서 실생할 수 있다.

중간언어 형태에 따른 4가지 분류
Polish 표기법(Postfix 표현 등), 3-주소 코드, 트리 구조 코드(AST 등), 가상 기계 코드(U-코드 등)

중간언어 생성
파서가 구문분석을 수행하고 결과로 다음단계에서 필요한 의미정보를 구성하여 출력한다.
방법1
생성 규칙에 해당하는 의미 수행 코드를 직접 기술.
파서에 의해 호출되어 실행된다.
각 생성규칙이 reduce될 때마다 의미 규칙이 수행되어 중간코드가 생성.
하지만, 이 방법의 문제점은 파싱 도중에 에러가 일어난 경우 그 때까지 행한 의미 행동들이 모두 무의미해진다. 
방법 2
방법 1 문제를 보완. 다음 단계에서 필요한 정보들만 구성(AST)
AST를 이용해서 중간 언어를 생성한다.
AST는 파스트리에서 중복되는 부분을 제거한 것. 필요한 정보들만 포함 한 것.
파스트리를 만들 때, shift할 때 단말노드가 만들어지고 reduce할 때 서브트리가 만들어지지만 
AST는 shift할 때 단만노드를 만들고 의미있는 생성 규칙으로 reduce할 때 서브트리가 만들어진다.

'공부 > 컴파일러' 카테고리의 다른 글

LR 구문 분석  (0) 2011.08.24
LL 구문 분석  (0) 2011.08.22
구문 분석 (syntax analysis)  (0) 2011.08.22
context-free grammar  (0) 2011.08.20
regular language  (0) 2011.08.20


Posted by skyjumps
공부/컴파일러2011. 8. 24. 20:02


Left to right scanning, Right parse.
 
파싱테이블 : 스택의 top과 현재의 입력 심벌에 따라 구문 분석 행동을 결정.
LR 파서의 네가지 행동 : Shift, reduce, accept, error
shift: 현재 상태에서 입력 심벌을 본 행동이 shift S이면 입력 심벌을 스택으로 이동하고 다음 상태 S도 스택에 넣는다.
reduce: 현재 상태에서 입력 심벌을 본 행동이 reduce A->α이면 스택에서  α 2배만큼 제거하고 A를 스택에 넣는다. 그리고 A에 대한 다음 상태를 스택에 넣는다.
accept: 주어진 입력이 올바른 스트링이다.

LR 파싱 테이블 만드는 방법 : Simple LR(SLR), Canonical LR(CLR), Lookahead LR(LALR)
SLR
LR(0) 아이템과 FOLLOW 집합을 이용하여 만든다.
LR(0) 아이템은 생성 규칙의 rhs에 .이 있는 생성규칙이다.
점 심벌 다음의 심벌을 mark 심벌이라고 한다.
CLOSURE 함수는 한 상태에서 보아야 되는 모든 LR(0) 아이템을 구하는 것.
마크 심벌이 논터미널일 경우 이 논터미널 생성규칙들을 LR(0) 아이템으로 만들어서 현재 상태에 추가 한다.
GOTO 함수는 한 상태에서 다른 상태로 가기 위해 사용. 
상태 I와 GOTO함수들이 파싱테이블을 구성한다.
CLOSURE로 한 상태를 구하고 그 상태의 GOTO함수를 만든다. GOTO함수의 결과가 이전 상태들하고 일치하는 것이 없을 때 새로운 상태가 된다. 
reduce 아이템에 대하여 그 생성 규칙의 lhs의 follow 심벌을 보고 reduce행동을 한다.  <- SLR의 특징.
한 상태에서 마크 심벌과 reduce 아이템의 follow가 같을 때, shift를 해야 할지, reduce를 해야 할지 결정할 수 없다. shift-reduce충돌
한 상태에서 두개 이상의 reduce 아이템의 follow 심벌이 같다면  어느 것을 reduce해야 할지 결정할 수 없다.  reduce-reduce충돌
문법이 모호하기 때문에 이러한 충돌이 발생한다.

CLR
Lookahead : 한 상태에서 어떤 논터미널 심벌 다음에 나올 수 있는 터미널. 상태 의존적인 follow. Follow가 lookahead를 포함.
reduce 아이템에 대한 reduce행동을 lookahead 심벌에 대해서 만드는 방법이 CLR.
CLOSURE구할 때 lookahead를 구해서 첨가한다. 한 아이템의 마크 심벌 다음에 오는 심벌의 FIRST가 그 심벌의 lookahead가 된다.  
lookahead때문에 파싱 테이블이 커진다. 그래서 lookahead를 이용하지만 테이블 크기는 작게 구성하는 LALR을 많이 사용한다.

LALR
방법1
core(아이템에서 lookahead를 제외한 부분)가 같은 것들끼리 묶는다.
SLR의 상태수랑 같게 된다. shift-reduce충돌은 일어나지 않지만  reduce-reduce충돌은 일어날 수 있다. 왜냐하면 shift는 코어에 따라 결정되는 것이지 lookahead에 의해 결정되는 것이 아니기 때문.
방법2
방법1은 lookahead 때문에 상태수가 많아지고 시간이 오래걸린다.
그래서 SLR에서 follow대신에 lookahead를 계산해서 사용한다.

모호한 문법
모호한 문법은 LR 문법이 될 수 없다.
하지만 연산순위나 결합 법칙 정보를 이용해서 하나의 행동을 선택하도록 함으로써 shift-reduce 충돌이나 reduce-reduce충돌을 해결한다.

 

'공부 > 컴파일러' 카테고리의 다른 글

중간언어  (0) 2011.08.24
LL 구문 분석  (0) 2011.08.22
구문 분석 (syntax analysis)  (0) 2011.08.22
context-free grammar  (0) 2011.08.20
regular language  (0) 2011.08.20


Posted by skyjumps
공부/컴파일러2011. 8. 22. 16:26


일반적인 top-down을 사용하면 backtracking이 생길 경우 느리니까, backtracking하지 않도록 결정적인 파싱 방법이 필요. 그러한 파싱 방법을 LL 파싱.

FIRST
논터미널 A로 부터 유도되어 첫번째로 나타날 수 있는 터미널의 집합.

nullable
논터미널 A가 ε를 유도할 수 있으면 A를 nullable하다. 

FOLLOW
생성규칙이 ε을 유도할 수 있으면 FIRST만 가지고는 생성 규칙을 결정적으로 선택할 수 없다.
논터미널 A 다음에 나오는 심벌에 따라 어느 생성 규칙으로 유도할 것인가를 결정한다. 

LL 조건
논터미널을 대치하기 위한 생성 규칙을 결정적으로 선택하기 위한 조건.
한 논터미널에 2개 이상의 생성규칙이 있을 때,
각 생성규칙의 FIRST가 달라야 하고,
한 생성 규칙이 ε을 유도할 수 있으면, 그 생성규칙의 FOLLOW와 다른 생성규칙의 FIRST가 달라야 한다.

LL방법을 실제로 사용하는 구문분석기
1) Recursive-descent
논터미널에 대한 유도를 각 논터미널별로 구현되어 있는 함수 호출로 처리.
논터미널에 적용할 생성 규칙을 정하기 위해 Lookahead를 조사. Lookahead는 각 생성규칙에서 첫번째로 유도될 수 있는 터미널들의 집합.
2) Predictive 파서
Recursive-descent파서는 생성규칙이 바뀔 때마다 프로그램을 다시 고쳐야 하는 단점이 있다.
Predictive파서는 파싱테이블만 수정하면 된다.
스택의 top과 현재 입력 심벌이 같을 경우 pop, 
expand : 스택의 top이 논터미널일 경우 생성규칙으로 바꿔서 역순으로 넣는다.
accept : 스택의 top과 입력이 모두 $인 경우, 파싱 성공
error

'공부 > 컴파일러' 카테고리의 다른 글

중간언어  (0) 2011.08.24
LR 구문 분석  (0) 2011.08.24
구문 분석 (syntax analysis)  (0) 2011.08.22
context-free grammar  (0) 2011.08.20
regular language  (0) 2011.08.20


Posted by skyjumps
공부/컴파일러2011. 8. 22. 15:37


구문 분석의 결과는 파스트리.
파스트리 만드는 순서
1) top-down, 2) bottom-up
top-down은 시작 심벌로부터 생성 규칙을 적용하여 좌측 유도해 나가는 방법.
bottom-up은 주어진 스트링으로부터 시작 심벌로 축약되어 가는 과정. 우측 유도에서 적용된 생성 규칙 번호의 역순.

파스트리의 루트노드는 시작 심벌이고, 중간 노드는 비단말 심벌, 단말 노드는 단말 심벌.
top-down 방식은 루드노드부터 만들어 나가고, bottom-up 방식은 단말 노드부터 시작하여 서브트리를 만들어 나간다.

추상구문트리(Abstract Syntax Tree) : 파스 트리에서 꼭 필요한 의미 정보만을 갖는 트리.

Backtracking
top-down 시작 심벌로부터 좌측유도 하다가 생성 규칙이 잘못 적용되었으면 그 생성 규칙에서 보았던 스트링을 다시 입력으로 보내고 다른 생성 규칙을 적용하여 유도를 해본다.

top-down 할 때 left-recursion이 있으면 무한루프에 빠진다.

direct left-recursion 없애기.
A->Aα|β, it means A= βα*
it equals
A-> βA'
A' ->αA'|ε  

indirect left-recursion 없애기
direct left-recursion으로 만든다음 없앤다.
direct left-recursion으로 만드는 알고리즘 :
논터미널에 순서를 매기고
논터미널의 생성규칙에 앞선 논터미널이 있으면 앞선 논터미널의 생성규칙을 대입한다.  

left-factoring
같은 심벌들을 prefix로 갖는 두 개 이상의 생성 규칙이 있으면 어떤 생성 규칙을 적용해야 할지 결정 할 수 없다.
공통된 앞부분을 새로운 논터미날을 이용해서 표현한다.
A->αβ|αγ <=> A->α(β|γ) <=> A->αA', A'->β|γ

bottom-up의 reduce
구문 분석 중에 나타나는 문장 형태의 일부분이 정의된 생성 규칙의 rhs와 같을 때, 이 생성규칙의 lhs로 대체하는 것.
reduce되는 부분을 handle이라고 한다.

shift-reduce 구문 분석
bottom-up의 일종.
스택과 입력 버퍼가 있다. 스택에 handle을 찾을 때까지 문법 심벌들을 유지하고, 입력 버퍼는 주어진 스트링을 가지고 있다.
shift는 입력 심벌을 스택으로 이동하는 것. reduce는 스택 top의 핸들을 생성규칙으로 축약하는 것.
accept는 주어진 스트링이 문법적으로 맞다는 것.

트리생성
파싱하면서 트리 만들 수 있다.
시프트할때 단말 노드를 만들고 reduce할 때 서브트리를 만든다.

'공부 > 컴파일러' 카테고리의 다른 글

LR 구문 분석  (0) 2011.08.24
LL 구문 분석  (0) 2011.08.22
context-free grammar  (0) 2011.08.20
regular language  (0) 2011.08.20
formal language  (0) 2011.08.20


Posted by skyjumps
공부/컴파일러2011. 8. 20. 16:42


정규문법은 제약이 많아 구문 구조를 표현하기 어렵다.

leftmost derivation, rightmost derivation.

derivation tree (유도트리)
context-free grammar는 문장 유도과정을 트리로 표현할 수 있다.

ambiguous
문법이 어떤 문장에 대해 두개 이상의 유도 트리를 가질 때 그 문법이 모호하다라고 한다.

필요없는 생성 규칙 (useless production) 제거
터미널 심벌로 유도 될 수 없는 생성 규칙들은 제거한다.

ε 생성 규칙 제거해야 될 때도 있다.

A->B같은 simple production(단일 생성규칙) 제거.

CNF(Chomsky Normal Form) 촘스키 정규 형태.
모든 context-free grammar는 CNF로 바꿀 수 있다.
CFG를 나타내는데 필요한 표기법을 간소화 하는데 유용하다.

CFG 표기법
BNF(Backus-Naur Form)
EBNF(Extended BNF)
syntax diagram (문법 흐름도) : 언어의 구문 구조를 쉽게 이해할 수 있도록 문법을 도식화.

PDA (Push Down Automata)
유한오토마타에  지나간 입력에 대한 결과를 알 수 있도록 스택을 추가한 것.
입력스트링을 유지하는 입력테이프와 스택, 전체 행동을 제어하는 유한 상태 제어가 있다.
현재상태와 입력과 스택을 보고 다음 상태와 스택에 들어갈 값을 정한다.
 시작상태에서 입력스트링을 다 봤을 때의 상태가 종결 상태(final state)이면 입력스트링은 이 푸시다운 오토마타에 의해 인식(accept)되었다고 말한다. 푸시다운 오토마타 언어는 이 오토마타에 인식되는 스트링의 집합이다.

PDA언어로 CFG를 구성할 수 있고, CFG로 PDA를 구성할 수 있다.

top-down 구문분석방법 : 시작 심벌로부터 아래로 내려가면서 스트링을 만든다.
bottom-up 구문분석방법 : 생성규칙의 rhs(right hand side)가 스택 top 부분에 나타날때까지 shift하다가 rhs가 되면 reduce를 한다.
shift는 입력에 있는 터미널을 스택 top으로 옮기는 것이고 reduce는 스택 top부분에 있는 생성 규칙의 rhs를 lhs로 바꾸는 것이다.

'공부 > 컴파일러' 카테고리의 다른 글

LL 구문 분석  (0) 2011.08.22
구문 분석 (syntax analysis)  (0) 2011.08.22
regular language  (0) 2011.08.20
formal language  (0) 2011.08.20
3장 context-free grammars & parsing  (0) 2011.07.27


Posted by skyjumps
공부/컴파일러2011. 8. 20. 11:58


정규언어는 토큰의 형태를 기술하는데 사용.
regular grammar(정규문법), regular expression(정규표현), finite automata(유한 오토마타)에 의해 표현한다.

정규문법 정의
A->aB 또는 A->a. A와 B는 논터미널, a는 터미널.
S ->ε이면 S가 다른 생성규칙의 오른쪽에 나타나지 않는다.
토큰의 구조를 표현하는데 사용. context-free문법으로도 만들 수 있지만 정규문법으로 더 쉽게 구현할 수 있다.
 
정규표현
기본 소자
Φ(공집합), ε(empty string을 나타내는 집합), terminal 심벌.  
union :  (e1)+(e2) 또는 (e1) | (e2)
concatenation : (e1)(e2)
closure : (e1)*

regular expression equation(정규표현식)
계수가 정규표현인 식.
정규문법을 정규표현식으로 나타낼 수 있고, 정규표현을 구할 수 있다.
정규문법과 정규표현은 같은 종류의 언어를 나타낸다.

유한오토마타
입력으로 스트링을 받아서 그 스트링이 그 언어의 문장이면 yes, 아니면 no을 답하는 인식기.
5개의 요소로 정의
유한개의 상태, 입력 심벌, 사상 함수(mapping function), 시작상태, 종결 상태(final state)
사상함수는 어떤 입력 a가 들어왔을 때, 상태 중에 하나를 결과(다음상태가 된다.)로 내보내는 함수. 전이함수라고 한다.

DFA(Deterministic FA)
전이 함수가 한 입력에 대한 다음 상태로 하나의 상태만을 갖는 경우. 

state transition diagram (상태 전이도)
유한 오토마타를 그림으로 나타낸것. 시작상태를 start, 각 상태는 노드,특히 종료 상태는 이중원인 노드. 입력에 대한 상태의 변화는 edges.

NFA (Non deterministic FA)
한 입력을 보고 다음 상태가 하나 이상 있을 수 있는 유한 오토마타.

NFA를 DFA로 바꿀 수 있다. NFA가 언어의 구조르 쉽게 표현할 수 있지만 프로그램으로 만들기는 어렵다. 그래서 DFA로 변환한다.
NFA에서 한 입력으로 갈 수 있는 노드들을 하나로 묶어서 하나의 상태로 본다.

ε-CLOSURE(s)
NFA에서 입력으로 ε을 가질 수 있을 때, 하나의 상태 s가 ε입력으로 갈 수 있는 모든 상태들의 집합.

DFA state minimization ( DFA 상태수 최소화)
종결상태와 종결아닌 상태로 나누고
각 그룹에서 할 일은 그룹에 있는 상태들이 각 입력에 대해 어느 그룹으로 가는지 조사하고 같은 그룹으로  가는 것들끼리 또 나누는 것.

정규문법을 유한 오토마타로 바꿀 수 있고,
유한 오토마타를 정규문법으로 바꿀 수 있다.

유한 오토마타가 인식하는 언어를 정규표현으로 나타낼 수 있다.
먼저 유한 오토마타로 정규문법을 구하고 그걸로 정규 표현을 얻는다.
또는 정규표현으로 유한 오토마타를 구할 수 있다.
정규 표현의 기본 소자(union, concatenation, closure 등)을 NFA로 표현하고, 간단화하고 DFA으로 변환한다.

펌핑 렘마
어떤 언어가 정규 언어가 아님을 증명하는데 사용.



 

'공부 > 컴파일러' 카테고리의 다른 글

구문 분석 (syntax analysis)  (0) 2011.08.22
context-free grammar  (0) 2011.08.20
formal language  (0) 2011.08.20
3장 context-free grammars & parsing  (0) 2011.07.27
2장 스캐닝 scanning  (0) 2011.07.26


Posted by skyjumps
공부/컴파일러2011. 8. 20. 11:03


언어는 스트링들을 원소로 같는 집합
문법은 정의된 언어를 어떻게 표현할 지 정한다.
derivation (유도)
한 스트링에서 생성규칙 (production rule)을 적용해서 다른 스트링으로 바뀌는 것. 
sententil form(문장 형태)
스트링이 논터미널 심벌과 터미널 심벌로 구성된 것.
sentence
문장 형태 중 논터미널을 포함하지 않은 것.

문법의 분류
Noam Chomsky (촘스키) 문법.
type 0 (unrestricted grammar, ug): 생성 규칙에 아무런 제한이 없다.  α -> β 에서 α가 empty 스트링이 아니다.
type 1 (context-sensitive grammar, csg): 생성규칙 α -> β에서 β의 길이가 α 의 길이보다 길다.
type 2 (context-fre grammar, cfg): 모든 생성규칙이 A -> α의 형태이다.  A는 한개의 논터미널, α는 논터미널과 터-미널로 구성된 스트링.
type 3 (regular grammar, rg): right-linear, left-linear. right-linear는 A->tB 또는 A->t.  left-linear는 A->Bt 또는 A->t. (A,B는 논 터미널, t는 터미널.)
정규문법에 의해 생성될 수 있는 언어를 정규언어. 정규언어는 유한 오토마타에 의해서도 표현될 수 있다.
context-free 문법에 의해 생성될 수 있는 언어를 context-free언어. context-free언어는 푸시다운 오토마타에 의해서도 표현될 수 있다.

'공부 > 컴파일러' 카테고리의 다른 글

구문 분석 (syntax analysis)  (0) 2011.08.22
context-free grammar  (0) 2011.08.20
regular language  (0) 2011.08.20
3장 context-free grammars & parsing  (0) 2011.07.27
2장 스캐닝 scanning  (0) 2011.07.26


Posted by skyjumps


MIPS
RISC  마이크로 프로세서.
RISC - CPU 명령어 갯수를 줄여서 하드웨어 구조를 간단하게 만드는 방식. 

메모리 주소가 바이트 단위가 아닌, 워드단위( 4바이트)


byte order

big endian: 가장 낮은 주소부분에 MSB가 온다.

little endian: 가장 낮은 주소부분에 LSB가 온다.


Stored program concept

명령어는 숫자로 표현되어 메모리에 저장된다.

명령어를 패치를 해서 레지스터로 로드한다.


Frame pointer

스택 프레임의 첫번째 워드를 가리킨다.

Stack pointer

다음 이용할 스택 주소를 가리킨다. 프로그램 실행 중에 계속 변한다.


Addressing Mode

MIPS명령어에서 주소 표현 어떻게 하는지

Register addressing - 레지스터 이름으로

Base or displacement addressing - 레지스터가 베이스주소고, 상수값의 offset이 주어진다.

Immediate addressing - 상수를 직접 넣는다.

PC-relative addressing - PC와 상수의

Pseudodirect addressing - 점프 명령어와 32bit 주소를 만들기 위해 26bit에 앞에 pc의 상위 4bit를 붙인다. 30Bitword 가리킬 수 있다.


Assembler

assembly 언어를 목적 파일로 변환해준다.

모든 레이블을 주소값으로 전환시켜준다.


목적 파일에는 headertext segment, data segment, relocation information, symbol table등이 있다.

헤더에는 이름 ,text size, data size등이 저장, text segment에는 코드저장, data segment에는 전역변수나, 스태틱 변수가 저장. Relocation information에는 명령어레이블, 라이브러리 명령어의 메모리 주소 저장, symbol table에는 레이블의 메모리 주소 저장.


링커

각 어셈블된 머신 랭귀지 프로그램들을 하나의 실행 가능한 프로그램을 결합시켜준다.


Static library

실행코드에 포함되어 있다. 사용되지 않아도 메모리에 포함된다.

Dynamic library

필요할 때 메모리에 로드된다.

DLL (dynamic link library)

반복해서 사용하는 코드들을 따로 바이러리로 만들어놓고, 필요할 때마다 사용하기 위해서 사용.


Loader

목적파일을 위한 메모리를 할당해주고, 스택에 argcargv같은 값을 저장. 레지스터 초기화, program entry point로 점프.

'공부 > 마이크로프로세서' 카테고리의 다른 글

코어의 수와 성능  (0) 2011.08.17


Posted by skyjumps
공부/네트워크2011. 8. 18. 20:35


node(host, router)간 링크를 통한 전송.
링크들이 가지고 있는 프로토콜이 다르다. 이더넷으로 전송되다가 무선랜프로토콜으로 전송되는 경우.
layer 2 패킷은 frame이라고 부른다. 데이터그램에 헤더랑 트레일러(trailer)를 붙인 것.
맥 어드레스 사용.
reliable data transfer 제공,
flow control 제공.
에러 검출/복구 제공. 신호감쇠나 소음에 의해 에러가 발생할 때.
half duplex, full duplex
network interface card(NIC, 랜카드)에서 링크레이어 구현

Error detection
Datagram 끝에  EDC(Error Detection and Correction bits)를 붙인다.
parity checking: 패킷 전체 1의 갯수가 홀(또는 짝)수가 되도록 맞춰주는 것.

인터넷 체크섬
트랜스포트 레이어 에러 체크
패킷을 16-bit로 나눠서 그것들의 합을 같이 보내고 받는 쪽에서도 계산해서 일치하면 에러가 없는 것.(하지만 있을 수도)

CRC (Cyclic Redundancy Check)
나머지 값을 패킷뒤에 붙어서 리시버쪽에서 어떤 값(센더와 리시버 둘 다 알고있는 것)으로 나눴을 때 나머지가 0이 아니면 에러 발생.
 
두가지 종류의 링크
1) point to point. 이더넷 스위치와 호스트 사이의 링크.
2) broadcast. 무선랜.

Multiple Access protocols
브로드캐스트 채널을 공유.
여러개 동시 전송이 있을 때 충돌 가능성.
multiple access protocol은 충돌이 발생하지 않게금 노드들이 패킷을 전송할 수 있게 조정하는 프로토콜.
control 채널이 따로 없다. data가 전송되는 채널과 같이 쓴다.

맥 프로토콜
세가지 분류
1) 채널 파티셔닝 - 채널을 작은 단위로 나눠서 각 단위를 노드에 배정(시간, 주파수, 코드)
2) 렌덤 엑세스 - 채널이 분할되지 않고 충돌을 허용. 충돌발생했을 때 복구 방법 제공.
3) Taking turns - 노드들이 돌아가면서 채널을 사용.

1) 채널 파티셔닝
TDMA (Time Division Multiple Access)
노드들이 라운드마다 한 패킷을 보낼 정도의 time slot를 얻는다.
 
FDMA (Frequency Division Multiple Access)
주파수로 채널이 분할.
각 노드는 고정 주파수를 배정 받는다. 

2) Random Access Protocols
노드가 보낼 패킷이 있으면 한 채널 다 사용해서 보낸다.
여러 노드가 동시에 사용하면 충돌 가능성.
어떻게 충돌을 감지하고 복구하는지 프로토콜이 필요.

slotted ALOHA
타임 슬랏으로 채널이 나눠지고, 노드는 한 타임슬랏이 시작될 때 패킷을 보내도록 동기화한다. 두개 이상 노드가 같은 타임슬랏에 패킷을 보내면 충돌. 충돌이 발생하면 확률 P로 패킷을 재전송한다.

pure ALOHA
타임 슬랏 없고 동기화 안한다.
slotted ALOHA보다 효율 떨어진다.

CSMA(Carrier Sense Multiple Access)
전송하기 전에 채널을 본다. 채널이 바쁘면 전송을 연기한다.
전송시간이 있기 때문에 채널을 봤을 때 그 당시에 idle이었다고 해도 충돌이 발생 할 수 있다.
CSMA/CD (Collision Detection
충돌이 감지되면 전송을 중지.
충돌이 어떻게 감지되나? 신호 세기를 측정. 보낸 시그널보다 신호세기가 크다면 충돌이 발생했음을 알 수 있다. 무선에서는 신호감쇠현상 때문에 판단하기 어려움.

3) Taking turns
공평하게 돌아가면서 채널 사용. 
Polling - master/slaves, master가 순서를 정해준다.
Token passing - token을 가지고 있는 노드가 채널 사용. 토큰은 한 노드에서 다른 노드로 전달됨.

Link layer는 맥 어드레스를 사용.
48bit.
IP처럼 계층적이지 않다.

ARP
다른 노드의 맥 어드레드는 어떻게 아는가? 자신의 ARP  table에 IP와 맥 어드레스가 매핑되어 있다.
맥어드레스가 ARP table에 없으면 어떻게 하는가? 상대방의 아이피 주소를 담아 ARP packet으로 브로드 캐스팅. 상대방이 자기 아이피임을 알고, 자신의 맥어드레스를 담아 ARP packet을 보낸다.

Ethernet
유선 랜 기술.
Star topology : 가운데 스위치가 있고, 각 노드는 스위치랑 이더넷프로토콜을 따른다. 각각의 노드가 다른 충돌 도메인을 가지므로 서로 충돌이 발생하지 않는다.
unreliable, connectionless. TCP를 사용하고 있으면 거기서 못받은 패킷을 매꾼다.
unslotted CSMA/CD를 사용한다.
jam signal : 충돌을 감지했을 때 다른 노드들에게 자기 패킷 충돌 발생했다고 알림.
exponential backoff: m번 충돌 발생했을 때, 2의 0승부터 m승-1까지 수 중에서 하나를 랜덤하게 선택해서 그만큼 기다린다. 

Hub
Physical layer의 장치이다.
신호 약해지면 증폭시켜 보내준다.
한 링크에서 비트들이 들어오면 허브가 다른 모든 링크에 그 비트들을 보내준다.
충돌이 발생할 수 있지만 정작 허브에서는 CSMA/CD가 없어서 각 호스트가 충돌을 감지한다.
frame buffering이 없다.

Switch
허브보다 똑똑한 link layer 장치.
store and forward 방식. 패킷을 다 받은 다음에 보낸다.
들어온 프레임을 버퍼에 저장했다가 맥어드레스를 보고 하나씩 보낸다. 보낼 때 CSMA/CD를 사용한다.
각 호스트가 스위치에 직접 연결된 링크를 가지고 있다. 충돌이 없다. 각 링크는 별도의 이더넷 프로토콜을 가지고 있다. 
스위치는 각 호스트가 스위치의 어떤 인터페이스에 연결되있는지 어떻게 알까? Self-learning!
self-learning
스위치는 스위치 테이블을 가지고 있다. 각 엔트리에는 호스트의 맥어드레스와 그 호스트로 갈 수 있는 인터페이스번호가 매핑되어 있다. 프래임을 받을 때마다 보낸 쪽의 맥 어드레스와 들어온 인터페이스번호를 테이블에 없으면 추가한다.
프래임을 포워딩할 때 테이블을 보고, 테이블에 있으면 그 인터페이스 번호로 포워딩하고 없으면 flooding(들어온 인터페이스를 제외한 모든 인터페이스에 프래임을 포워딩) 한다. flooding을 하면 해당되는 호스트에 응답이 오는데, 그 응답을 보고 테이블에 추가한다. 

스위치와 라우터비교
스위치는 링크레이어, 라우터는 네트워크 레이어.
스위치는 스위치테이블, 라우터는 라우팅 테이블을 가지고 있다.
스위치는 self-learning, 라우터는 라우팅 알고리즘이 있다. 

'공부 > 네트워크' 카테고리의 다른 글

Network Layer  (0) 2011.08.15
Transport Layer  (0) 2011.07.28
Application layer  (0) 2011.07.23


Posted by skyjumps


코어가 많이 늘어난다고 해서 그에 비례하는 성능이 생기는 것은 아니다.
왜냐하면 코어가 많아질 수록 코어 간에 공유되는 메모리가 많아지고 정확하게 처리하기 위한 작업이 복잡해지기 때문이다.

참고사이트
http://geekeno.wordpress.com/category/development/parallel/ 

'공부 > 마이크로프로세서' 카테고리의 다른 글

MIPS 요약  (0) 2011.08.19


Posted by skyjumps