[Cloud computing] 6. Parallel & Distributed

Reference

1. Thomas Erl_ Zaigham Mahmood_ Ricardo Puttini - Cloud Computing_ Concepts, Technology & Architecture-Prentice Hall,

2. Cloud Computing class by Professor Heonchang-Yu of the Department of Computer Science and Engineering at Korea University

3. Open Source material : opencourses.emu.edu.tr, WEEK 5 - APPLICATION OF PETRI NETS

 

cloud comtuting의 major milestone 세 가지

• mainframe computing
• cluster computing
• grid computing

+) Peer to Peer system

 

---

1. Historical development

mainframe computing

• 대규모 데이터 이동, I/O 작업에 특화된 강력하고 신뢰성이 높은 컴퓨터
• distributed system 아님! , 여러 processor를 사용하여 큰 계산 능력 제공

cluster computing

• 여러 대의 컴퓨터들이 고대역폭 네트워크로 연결된 집합
• 쉽게 확장 가능

Grid computing

• 대규모 작업을 수행하기 위해 컴퓨터의 처리 능력을 한 곳으로 모아 중요한 업무에 집중 사용할 수 있게 해주는 기술
• 지리적으로 분산된 cluster의 집합체 → 서로 다른 조직에 속한 cluster들이 계산 능력을 공유
• 여러 독립 컴퓨터의 리소스를 통합하는 distributed computing의 일종

Peer-to-Peer System

• 중앙 서버 없이 computer끼리 연결하여 data를 주고 받는 것
• Self-organizing and decentralized
• scalable, resilient

 

Distributed and Grid computing

유사점

1. Resource sharing
2. Heterogeneity & concurrency
3. Openness & transparency
4. Redundancy
5. Scalability

차이점

1. definition : broader vs narrower
2. scope of application : broader(gps, 인터넷) vs narrower(빅데이터 분석, AI 모델링)
3. Model and architecture : 다양함(grid, cloud, cluster computing) vs specific computing model

 

---

2. Parallel and Distributed Computing

병렬 computing은 분산 computing의 한 종류이다.

• Parallel → Coupled system: 모든 processor가 memory 공유
• Distributed → 전부 포함 : processors on (1)different nodes, (2) same computer, (3) cores within same processor
• Parallel processing : multiple processor가 동시에 다량의 task 처리

Hardware architectures for parallel processing

PE : processing element

(1) Single-instruction, single-data (SISD) systems

(2) Single-instruction, multiple-data (SIMD) systems

(3) Multiple-instruction, single-data (MISD) systems

(4) Multiple-instruction, multiple-data (MIMD) systems

• shared memory MIMD machine : tightly coupled multiprocessor system -모든 PE가 단일 memory에 연결되고, 모두 접근 가능
• distributied memory MIMD machine : loosely coupled multiprocessor system - 모든 PE에 로컬 메모리가 있고, 네트워크를 통해 PE간 통신

 

Approaches to parallel programming

병렬 컴퓨팅 : 큰 problem을 작은 problem으로 나누어서 동시에 해결할 수 있다

(1) Data parallelism

• 분할 정복 기술을 통해서 데이터를 여러 set으로 분리하고 각 set에 동일한 명령을 사용하여 서로 다른 PE에서 이를 처리
• SIMD 모델에 적합

(2) Process parallelism

• 여러 processor가 처리

(3) Farmer and worker model

• 작업을 분배한다. 한 process가 master가 되고 나머지 모든 PE가 slave가 된다.
• master가 slave에게 작업을 할당하고, 완료 시 master에게 알려서 결과를 수집한다.

 

parallelism으로 얻을 수 있는 benefit이 얼마나 되는가

• 연산의 속도는 system cost의 제곱근에 비례한다. → 선형 증가 X
• n개의 processor → k* log(N)배

 

---

3. Parallel and Distributed Systems

Amdahl’s law

• speed-up of the parallel computation : S(N) = T(1)/T(N) → 1/N이 안 나옴
• ⇒ (dependency 때문에 병렬 수행이 불가능한 경우가 존재하기 때문)

 

Modeling concurency with Petri nets (PNs)

4가지로 구성

• Token : 작은 꽉 차 있는 원으로 표현됨. 화살표를 따라 움직이면서 프로세스를 진행시키는 역할
• Place : 원으로 표현됨. Place는 token을 소유할 수 있다.
• Treansition : 사각형으로 표현됨. 이벤트 로그에서의 액티비티를 뜻한다. transition은 Token을 만들어내거나 소비한다.
• Arc : 화살표로 표현된다. Transition과 place을 연결하는 역할을 하며, token은 Arc를 따라 이동한다.

 

Enabled(준비)과 Fire(실행)

• Enabled : transition이 실행(fire)될 수 있도록 준비된 상태를 의미한다. transition으로 들어오는 모든 place들에 token이 한 개 이상 있는 상태이다.

⇒ 만약, 2개 이상의 place에 연결된 transition의 경우, 한 쪽이라도 token이 없는 place가 있을 때는 enabled 상태가 아니다.

• Fire : transition이 enabled되었을 때 그 transition이 실행되는 것이다. 이때 모든 input place에 있는 한 개의 token들은 소비되고(consume), 모든 output place에 한 개의 token이 만들어 진다.(produce)

⇒ transition에서 event가 발생함으로써 상태가 변화

⇒ 즉, input place가 1개라도 out place가 여러 개라면, token이 1개만 소비되었지만 여러 개의 token이 생성되는 것이다.

⇒ Arc에 Token 숫자를 명시한다!

 

Example 1,2,3

 

Example 4,5,6

마지막 예제의 경우, shared memory에서 process간 동시성 문제를 해결하는 locking 방법을 petri net으로 나타낸 것입니다.

좀 더 자세히 살펴보면,

• 최대 k개의 process가 동시에 reading 가능
• 1개의 process가 writing 할 때, 아무도 reading하거나 writing 하지 못하고 오직 그 process만 wirting할 수 있다.

⇒ reading은 data를 단순히 조회하는 것이지만, write의 경우 data가 변경되므로 lock을 걸어서 동기화를 시켜주는 것이다.

 

---

4. Concepts of Distributed systems

Definition

• message passing으로 소통하는 hardware, software components
• 독립적인 computer들이 message passing 방식으로 조직화 된 system

Concurrency

• 자원을 공유하면서, 사용자들이 각자의 work를 동시에 수행
• 자원을 공유하고 동시에 실행되는 program들 간 coordination 중요
• core 1개, multithread → 한 번에 하나의 thread만 core 할당
• message passing 방식으로 동기화
• Deadlock 발생 가능
• Livelock 발생 가능 (마치 길에서 마주칠 때 계속 같은 쪽으로 서로 비켜서서 길이 막히는 경우와 같다)

Consequences

No global clock

• global하게 공유되는 clock이 없다.
• local clock들을 동기화하는 것은 불가능하다
• 따라서 일종의 “번호표”를 사용. Order가 중요한 것

Independent failures

• 네트워크가 끊어지면 해당 computer는 고립됨, 해당 computer의 program들은 네트워크가 끊어진지도 모를 수도 있다.
• 한 computer에서 이상이 생겨 program이 비정상적으로 종료되어도, 다른 computer들은 이를 즉시 알아채지 못함

 

---

5. Issues

(1) Heterogeneity

• heterogeneous collection of computers and network 위에서 사용자들이 service에 접근하고 application을 run시킬 수 있어야 한다.

⇒ 이를 위해 Middleware가 masking, conciling 해야 한다.

• Middleware : 아래 단의 heterogeneity을 masking 하는 programming abstraction을 제공하는 소프트웨어 layer

⇒ Local OS간의 heterogeneity를 Middleware layer을 통해 추상화하여 극복

(2) Openness

• 다양하게 확장이 가능하다.

(3) Security

Confidentiality - 인증 안 된 유저로 부터 보호

Integrity - 변조로 부터 보호

Availability - 자원 접근 보호

⇒ Ddos 공격 등 보호 필요

(4) Scalability

• 물리적 자원의 비용을 조절

자원에 대한 수요가 증가할 때, 적당한 비용에서 system을 확장시켜야 한다.

사용자가 n명인 시스템을 확장하려면 사용자를 지원하는 데 필요한 물리적 리소스의 양이 **최대 O(n)**여야 한다.

• Performance loss를 조절

hierarchic(계층) 구조를 사용하는 알고리즘은 linear 구조를 사용하는 알고리즘보다 더 잘 확장된다. 그러나 hierarchic 구조에서도 크기가 증가하면 성능이 다소 저하된다.

• Preventing software resources running out

자원이 소진되지 않도록 주의

• Avoiding performance bottlenecks

병목 구간이 생기지 않도록 주의

(5) Failure Handling → Redundancy 적용

• failures 탐지
• Masking (hiding) failure : 사용자는 apllication을 사용하면서 failure를 못 느끼도록 masking
• Tolerating failure : 실패해도 계속 동작하도록
• Recovery from failure : check point 지정해서 recovery

(6) Concurrency

• multiple client의 request를 동시에 수용
• data가 consistent하기 위해 동기화 필요
• semaphores 사용 : 공유하는 자원에 여러 process or thread가 접근하는 것을 막는다.

(7) Transparency - 투명성

• Access : 동일한 operation으로 자원에 접근
• Location : 물리적 위치에 상관없이 자원에 접근
• Concurrency : 간섭없이 여러 process들이 자원을 공유하며 동시에 실행
• Replication : 안정성과 성능을 높이기 위해 여러 자원의 복제본 사용, 복제본끼리는 서로 존재를 모름
• Failure : failure을 conciling
• Mobility : 사용자, 프로그램에게 영향을 주지 않고 자원의 이동
• Performance : 성능 향상
• Scaling : system 구조 변경 없이 곧바로 확장 가능
• Network : network을 통해서 access, location transparency 가능