01204434 – Parallel and Cloud Computing

เนื้อหาทั้งหมดต่อจากนี้ถูกเขียนโดยนิสิตภาควิชาวิศวกรรมคอมพิวเตอร์

คณะวิศวกรรมศาสตร์ มหาวิทยาลัยเกษตรศาสตร์ รุ่นที่ 23

โดยเป็นเนื้อหาจากบทเรียนทีเกิดจากการจดบันทึกในห้องเรียนและศึกษาเพิ่มเติมจากนอกห้องเรียน

โดย มีจุดประสงค์เพื่อเป็นแนวทางในการเรียนรู้ของผู้ที่สนใจหรือรุ่นน้องรุ่น ถัดๆไป โดยมีการคงสภาพของเนื้อหาทั้งหมดไว้ทุกประการ รวมถึง คอมเมนท์ ส่วนที่ไม่ใช่เนื้อหาอื่นๆ เป็นต้น

อย่างไรก็ตาม

ในกรณีที่ถูก นำไปใช้หรือนำไปอ้างอิงด้วยวิธีใดวิธีหนึ่งก็ตาม ในกรณีที่เนื้อหาไม่ถูกต้อง ไม่เหมาะสม ผู้เขียนจะไม่ขอรับผิดชอบใดๆทั้งสิ้น ขอให้อ่านด้วยวิจารณญาณของผู้อ่านเอง

ท่านสามารถอ่านเลคเชอร์ฉบับ Document ได้ที่นี่

===============================================

204434 Parallel

Para. & Dist. Sys.

Course Information

Instructor: ~pu

Office: Rm. 410

Phone: 9428555 #1423

Grading

MT 40, Fin 40, Project 20

Text

Quinn. Parallel Programming in C with MPI and OpenMP (2003)

Lecture 1: Overview

Von Neumann Bottleneck

เป็นคอขวดที่เกิดจาก bus ในสถาปัตยกรรม von Neumann

Pipelining

การแก้ปัญหาในยุคแรกๆ ของสถาปัตยกรรมคอมพิวเตอร์คือการทำ pipelining (ถ้ายังจำจากวิชา architecture ได้ ก็จะคล้ายๆ กับการจ้างคนสี่คนมาซักผ้า คนหนึ่งซัก คนหนึ่งตาก คนหนึ่งรีด คนหนึ่งเอาไปเก็บ เป็นต้น แทนที่จะจ้างคนเดียวทำเทียวไปเทียวมา)

ข้อดีของ pipelining คือเร่งการทำงานให้ทำงานได้ปริมาณมากขึ้น โดย speed-up หาได้จาก

โดยที่ c คือจำนวน stage และ n คือจำนวน instruction ซึ่งทำให้เมื่อ n หรือจำนวน instruction เพิ่มมากๆ จะทำให้ c/n เป็นศูนย์ เราจึงได้ว่า speed-up เท่ากับจำนวน stage ของระบบ

Overclocking

เรื่องธรรมดาๆ คงเข้าใจได้ไม่ยากอยู่แล้ว ก็คือทำไปเรื่อยๆ จนกระทั่งมันเริ่มใช้ไม่ได้ก็เอา overclock ออกไป แค่นั้นเอง

Massively Parallel Machine

เป็นระบบที่สามารถทำงานได้มาก โดยใช้ processor มาทำงานขนานกัน

http://en.wikipedia.org/wiki/Massively_parallel_(computing)

Beowulf Cluster

ไม่ใช่เทคโนโลยีใหม่ แต่เป็นการใช้คอมพิวเตอร์ระดับพีซีธรรมดามาทำเป็นคลัสเตอร์ ทำให้ได้คลัสเตอร์ในราคาถูกลงมา ซึ่งนำไปสู่การถือกำเนิดของคลัสเตอร์คอมพิวติง

Grid Computing

เกิดจากการเชื่อมโยงระบบงานบนหลายๆ ไซต์พร้อมกันด้วยมิดเดิลแวร์ต่างๆ นำไปสู่การตั้งศูนย์กริดแห่งชาติในประเทศต่างๆ แต่ก็ไม่เป็นที่แพร่หลาย เนื่องจากธรรมชาติของกริดที่ไม่ได้ทำงานกับแอพพลิเคชันอะไรก็ได้ แต่เน้นไปที่การทำงานทางวิทยาศาสตร์เป็นหลัก

The 3.5GHz Problem and the Rise of GPU

มีการรื้อฟื้น multiprocessing กลับมาหลังจากที่ซีพียูในยุคนั้นร้อนมากเกินไป กลายเป็น multicore ต่อมาการคำนวณจึงเข้าไปอยู่ใน GPU ซึ่งทำงานได้ลำบากเพราะเป็นการเข้าถึงฮาร์ดแวร์ NVIDIA จึงสร้าง CUDA ขึ้นมา

แต่ GPU ก็ไม่ใช่คำตอบ เพราะการคำนวณแบบขนานไม่สามารถทำงานในระบบเก่าได้ จึงต้องพอร์ตไป แถมยังมีข้อจำกัดเรื่องการย้ายและเข้าถึงหน่วยความจำ ทำให้เสียเวลาที่ I/O มาก

Intel Many Integrated Core (Intel MIC) and AMD Fusion

เป็นการกลับมาของ Intel ซึ่งใช้การยัดคอร์จำนวนมากๆ ลงไป พยายามที่จะจัดการกับข้อจำกัดของ GPU ซึ่งแน่นอนว่าไม่ใช่การฆ่า GPU อย่างเด็ดขาด แต่เป็นการสร้างพื้นที่ให้กับตัวเอง

จุดเจ๋งของมันคือสามารถทำงานบน business setting ได้ดี เพราะงานประเภท service จำเป็นที่จะต้องใช้ CPU ด้วย เมื่อเรายัดคอร์ลงไปมากๆ ได้จะเกิด economy of scale ทำให้ราคาถูกลง

AMD จึงตอบโต้อีกครั้งโดยการเข็น AMD Fusion ออกมา โดยเป็นความพยายามที่จะเอา GPU ไปยัดใน CPU ด้วย

OpenCL

OpenCL ถูกหนุนหลังโดยแอปเปิล โดยมี programming model ที่ทำงานได้ทั้งบน many-core และ GPU ทำให้ OpenCL ทำงานได้หลากหลายกว่าเมื่อเทียบกับ CUDA ที่ทำงานได้เฉพาะบน GPU อย่างเดียว

Cloud Computing

คำว่าคลาวด์มาจากตัว network เองที่มักถูกวาดเป็นรูปก้อนเมฆ แบ่งออกเป็นสามเลเยอร์คือ

  1. IaaS เช่น VM
  2. PaaS เช่น programming
  3. SaaS เช่น application หรือ webmail ต่างๆ

การสร้าง data center ไว้ที่เดียวแล้วสร้าง cloud ขึ้นมาก็มีประโยชน์ การทำ mobile computing ก็ใช้ cloud ด้วย ซึ่งงานหลายๆ อย่างเราสามารถโยนมาทำบน cloud ได้ เพื่อให้ใช้พลังงานได้ดีขึ้น เช่น การรันงานบางอย่างไม่ต้องรันเอง แต่ให้ทำบน cloud ได้ เช่น การแต่งรูปจากกล้อง

Big Data

การย้ายไฟล์หรือเนื้อหาปริมาณมากๆ ใช้เวลานาน เพราะ I/O ไม่เร็วพอ ทำให้ทำงานได้น้อย เทคนิคที่ใช้กันจึงกระจายไปไว้บนหลายๆ จุดที่มีทั้ง I/O และ compute เพียงพอ

Cluster and Grid

Cluster คือการตั้งเครื่องไว้ที่เดียวกัน เชื่อมโยงโดย high-speed network

แต่ Grid เป็นระบบที่ distributed โดยกระจายงานออกไป ต่างคนต่างทำ แล้วดูดงานกลับมา

Parallel -> ทำให้เร็ว

Distributed -> ทำให้ throughput มากขึ้น

Grid and Cloud

Cloud เป็นการทำงานตรงกลางแล้วให้ผลออกไป

Grid เป็นการกระจายงานออกแล้วรอรับผลกลับมา

Grid จะไม่ตาย เพราะมีความได้เปรียบที่เราเก็บ data กระจายกันแล้วต่างคนต่างทำได้

Vertical and Horizontal

Vertical Scalability คือการทำงานให้ “เร็ว” รองรับงานที่ต้องการความ “เร็ว” เช่น การทำ server

Horizontal Scalability คือการทำงานให้ “เยอะ” เช่น การประมวลผลง่ายๆ แต่เยอะ

Lecture 2

ทำไมคอมพิวเตอร์ต้องเร็วขึ้น

เพื่อให้แก้ปัญหาต่างๆ ได้เร็ว หรือทำให้แก้ปัญหาได้มากขึ้น (ปัญหาใหญ่ขึ้น) เช่น

  1. การพยากรณ์อากาศซึ่งเป็นปัญหาที่มีขนาดใหญ่ หากต้องการทำงานบนพื้นที่ 2000*1000km (2*106 km2) สมมติว่าหากใช้เวลาตารางกิโลเมตรละนาที (จริงๆ ต้องมีปริมาตรด้วย) จะใช้เวลารวมกันประมาณ 380 ปี 3 เดือน ยิ่งถ้าเพิ่มความละเอียดเข้าไปอีกก็จะมีค่าใช้จ่ายสูงขึ้นไปอีก
  2. ปัญหาจำพวกของไหล (fluid)

นอกจากนี้ความเร็วที่สูงขึ้นยังทำให้ออกแบบได้เร็วขึ้นด้วย

Parallel Computing

คือกระบวนการใช้ parallel computer (คือระบบ multiprocessor ที่รองรับ parallel programming) ในการแก้ปัญหาต่างๆ

Message Passing Interface – MPI, and OpenMP

เป็นหนทางของเราในการทำ parallel computing ซึ่งเราจะใช้ในการทำงานกับซีพียูได้ CUDA ก็มีพื้นฐานอยู่บนนี้เช่นกัน

พัฒนาการของ supercomputing

Computing เกิดจากความจำเป็นในอดีตที่จะคำนวณว่าการยิงปืนใหญ่ในสงครามโลกครั้งที่สองต้องทำอย่างไร ใช้อะไรบ้าง เพื่อมาทดแทนการคำนวณด้วยคน

ในเชิงพาณิชย์ก็มีการนำมาใช้งาน เช่น การหาปิโตรเลียม (โดยการคำนวณคลื่นดิน หรือ seismic wave จากการระเบิดสำรวจ) หรือการออกแบบยานยนต์ เมื่อมีองค์กรใดนำมาใช้ องค์กรอื่นก็มาแข่งกันด้วย

ในปัจจุบันก็นำมาใช้เล่นหุ้น หรือการตัดสินใจทางธุรกิจต่างๆ ในปัจจุบันคอมพิวเตอร์เป็นสิ่งที่พัฒนาเร็วที่สุดในสังคมมนุษย์

Problems with supercomputers

การสร้าง Parallel computer ทำให้ได้ความเร็วเท่ากับ Supercomputer แต่ข้อจำกัดบางอย่างทำให้ (traditional) supercomputer ยังมี I/O ที่ดีกว่า OS ที่ดีกว่า เป็นต้น เพราะมันใช้ระบบของมันเองทั้งหมด แต่มีแค่ไม่กี่บริษัทเท่านั้นที่ยังทำ (wide-sense) supercomputer ขายอยู่ได้

Beowulf

ที่ NASA (Sterling & Becker) มีการนำเครื่องพีซี 486DX100 มาต่อกันด้วย FastEthernet ลงระบบปฏิบัติการลินุกซ์ (เกือบได้ใช้บีเอสดีแล้ว แต่เกิดดราม่ากันก่อน) และใช้ MPI ทำให้รัน application บางอย่างได้ในราคาที่ไม่แพง

Concurrency

  1. Data Dependency
  1. Dependence Graph อธิบายว่ากิจกรรมการทำงานของเรามีการส่งต่อข้อมูลอย่างไร เรานำมาใช้พิจารณาว่าอะไรทำพร้อมกันได้บ้าง

Data Parallelism

งานเช่น

a[i] = b[i] + c[i]

สามารถทำได้พร้อมๆ กันสำหรับทุกๆ i อยู่แล้ว ทำให้มีลักษณะดังนี้

  1. ทุกๆ processor ทำงานที่เหมือนกัน ต่างกันแค่ข้อมูล
  2. ทำงานแบบ sync. หรือ async. ก็ได้
  3. fine-grained parallelism คือการแตกการทำงานลงไปให้ละเอียดที่สุด

Functional/Control/Job Parallelism

a = 2

b = 3

m = (a+b)/2

s = (a*a+b*b)/2

v = s-m*m

ในงานนี้จะเห็นว่าเราสามารถหา m และ s พร้อมกันได้ แต่งานมันไม่เหมือนกัน การแบ่งงานก็จะแบ่งให้พอๆ กันสำหรับทุก processor (ไม่จำเป็นต้องเท่ากัน เพราะงานแต่ละอย่างมีความยากไม่เท่ากัน)

ทั้งนี้ การทำงานส่วนใหญ่จะเป็น data parallel ทำให้ทำงานได้ง่ายกว่า

Parallelism in Data Clustering

Data clustering เป็นการแบ่งข้อมูลออกมาเป็นกลุ่มที่มีคุณสมบัติบางอย่างเหมือนกัน ซึ่งสามารถช่วยเร่งความเร็วในการค้นหาได้

กระบวนการ clustering คือการสร้างเวกเตอร์ของคุณสมบัติต่างๆ ที่ต้องการออกมาก่อน แล้วกำหนดจุดกึ่งกลางลงไปแบบสุ่มตามจำนวนกลุ่ม จากนั้นเราทำขั้นตอนต่อไปนี้ซ้ำๆ กัน

  1. แต่ละจุดศูนย์กลาง “แย่ง” กันเอา data node ที่ใกล้ที่สุดมาใส่ โดยใช้ vector distance
  2. จาก data node ทั้งหมดเอามาคำนวณ center ใหม่

งานเหล่านี้ทำบนข้อมูลปริมาณมากๆ อยู่ตลอด

วิธีการทำที่เร็วก็คือ ให้บางตัวไปอ่าน document database ก่อน อารมณ์ประมาณ pipelining

การเขียนโปรแกรมขนาน

  1. ทำคอมไพเลอร์ให้มีความสามารถในการสร้างโปรแกรมแบบขนานได้
  2. ภาษาที่มีคำสั่งที่จะไปรันงานดังกล่าว
  1. เพิ่มคำสั่งใหม่หรือไลบรารีโดยไม่เปลี่ยนคอมไพเลอร์ เช่น CUDA
  2. สร้างภาษาใหม่

แผน 1: ขยายคอมไพเลอร์ให้เขียนขนานได้

สามารถทำให้โปรแกรมเก่าทำงานได้ทันที ใช้ง่าย แต่ก็มีโอกาสผิดพลาด หรือมองได้ยาก

แผน 2: เพิ่มฟังก์ชันในภาษา

ทำง่ายกว่าเร็วกว่าไม่เปลืองแรงวิจัย ใช้ได้เลยเพราะไม่ได้แก้ตัวภาษา แต่เนื่องจากเราไม่ได้ทำงานกับคอมไพเลอร์ ทำให้คอมไพเลอร์ช่วยหาที่ผิดพลาดหรือแก้บั๊กยาก

แผน 3: สร้าง programming layer

  1. lower layer
  1. คำนวณ ฯลฯ
  1. upper layer
  1. การกระจายข้อมูล ฯลฯ

แผน 4: สร้างภาษาขนาน

จะสร้างใหม่เลยเช่น occam แต่สุดท้ายก็ไปไม่รอด มักจบลงที่การขยายภาษาเก่าอยู่ดี เช่น C* เป็นต้น ทำให้สามารถนำความขนานไปให้คอมไพเลอร์ได้ดี เร็วขึ้น แต่ต้องสร้างคอมไพเลอร์ใหม่ อาจได้ภาษาที่ไม่เป็นมาตรฐาน และแรงต้านสูง

ปัจจุบัน low level approach ถูกใช้มากที่สุด แม้ว่าจะใช้ยากพอสมควรก็ตาม

Lecture 3

workshop

http://maeka.cpe.ku.ac.th/drupal/?q=node/8

ssh yourname@maeka.cpe.ku.ac.th

Submit your job

qsub myjob.sh

Check it with qstat

If it goes down → tell support

Task/Channel Model

Parallel คือเซตของงาน (task) งานแต่ละงานมีโปรแกรม (code) หน่วยความจำ และกลุ่มของ I/O ซึ่งงานต่างๆ ก็สามารถคุยกันผ่านช่องทาง (channel) ต่างๆ ได้

Foster’s Methodology

ประกอบไปด้วยสี่ขั้นตอน ได้แก่

Partitioning

คือการแบ่งปัญหาที่ใหญ่ให้เล็กลง

  1. Domain Decomposition
  1. แบ่งปัญหาตามข้อมูล
  1. Functional Decomposition
  1. แบ่งปัญหาตามการทำงาน เช่น แบ่งตามขั้นตอน ซึ่งถ้าหากแต่ละขั้นตอนใช้ข้อมูลแตกต่างกันก็สามารถทำงานพร้อมกันได้

Data and functional decomposition

โดยปกติแล้ว การแบ่งงานของเราจะ

  1. ทำให้มี primitive task อย่างน้อย 10 เท่าของจำนวนหน่วยประมวลผล
  2. ลดการซ้ำซ้อนให้มาก
  3. ทำให้ task มีขนาดพอๆ กัน
  4. จำนวนงานควรขยายตามขนาดปัญหาได้

Communication

เราจะต้องดูว่า งานต่างๆ จะต้องการค่าจากงานอื่นๆ หรือไม่ อย่างไร เช่น ในการคำนวณแบบ finite element เราต้องการค่าจากช่องกริดข้างๆ ด้วย ในกรณีนี้คือ local communication

  1. งานแต่ละงานใช้ค่าจากงานอื่นๆ จำนวนน้อยๆ
  2. สร้าง channel ขึ้นมาว่าข้อมูลจะไปทางไหนบ้าง

ในทางตรงข้ามกันก็จะมี global communication ซึ่งใช้ค่าจากงานอื่นๆ มาก เราไม่ควรสร้าง channel ในตอนนี้

เราควรได้การสื่อสารที่

  1. มีความสมดุล ไม่หนักไปทาง task ใดๆ
  2. ทำให้ local มากที่สุด
  3. ทำให้การสื่อสารพร้อมๆ กันได้มาก
  4. ในระหว่างที่ไม่ได้สื่อสาร สามารถคำนวณพร้อมกันได้

Agglomeration

คือการรวม task ให้ใหญ่ขึ้น เพื่อให้ปรับปรุงสมรรถนะของงาน และรักษา scalability ไว้ เพราะเราไม่ต้องการ communicate ให้บ่อยเกินไป แต่ใช้เวลาคำนวณให้มากขึ้น (เพราะ communication เป็น overhead)

โดยปกติใน MPI เรามักจะพยายาม agglomerate ให้เหลืองานใหญ่ๆ ชิ้นเดียวต่อ processor

การกระทำนี้จะทำให้ parallelism ลดลง แต่ก็จะมีจุดคุ้มอยู่ที่ทำให้ได้ประสิทธิภาพ

Agglomeration Checklist

  1. เพิ่ม locality
  2. การคำนวณที่เพิ่มขึ้นต้องใช้เวลาน้อยกว่าการสื่อสารที่ลดลง
  3. data replication ไม่กระทบ scalability
  4. งานที่ agglomerate แล้วควรจะมีค่าใช้จ่ายทางการคำนวณและการสื่อสารพอๆ กัน
  5. จำนวนงานควรจะเพิ่มตามขนาดปัญหา

Mapping

คือการบอกว่าจะเอางานไหนไปรันบน processor ไหน

  1. Centralized Multiprocessor คือการทำ mapping บน OS
  2. Distributed Memory System คือการทำ mapping เอง

แล้วทำไมเราไม่ mapping ด้วย OS ไปเลย? เพราะงานของเราเป็นงานที่มี coordination อยู่ การควบคุมการทำงานโดยโปรแกรมเมอร์จะได้ความเร็วดีกว่า ไม่เหมือนกับการทำงานปกติ

แล้ว parallel คืออะไร? ของอย่างเดียวหลายคนทำเร็วขึ้น เช่น rendering

แล้ว distributed คืออะไร? คือของหลายอย่างหลายคนทำ ได้ throughput มากขึ้น (ไม่ได้เร็วขึ้น แต่ได้งานมากขึ้น) โดยปกติ distributed จึงใช้งานเพื่อสร้าง throughput

กฎข้อแรกของ parallel: ถ้าไม่ parallel ได้ก็จะดี (เช่น ไปทำเป็น distributed แทน)

Conflicting Goals

  1. Maximize processor utilization
  2. Minimize interprocessor communication

ปัญหาของ mapping แก้ได้โดยใช้ graph partitioning ที่ทำให้เหลือ edge ระหว่าง partition น้อยที่สุด

Mapping Decision Tree

  1. Static number of tasks
  1. Structured communication
  1. Constant computation time per task
  1. Agglomerate tasks to minimize comm
  2. One task per processor
  1. Variable computation time per task
  1. Cyclically map tasks to processors
  1. Unstructured communication
  1. Use a static load balancing algorithm
  1. Dynamic number of tasks
  1. Frequent communications
  1. Use dynamic load balancing
  1. Many short-lived tasks
  1. Use run-time scheduling

Checklist

  1. ดูว่าจะมีกี่ task per processor
  2. ประเมินว่าเป็น static หรือ dynamic
  3. ถ้า dynamic ตัว task allocator ต้องไม่เป็น bottleneck
  4. ถ้า static ต้องทำให้ tasks : processor > 10:1

Case Studies

Boundary Value Problem

เป็นปัญหาทางคณิตศาสตร์-วิศวกรรมที่เจอได้บ่อย ซึ่งเกี่ยวกับการเปลี่ยนแปลงของค่าในช่วงค่าหนึ่ง ในสไลด์อธิบายเกี่ยวกับการเอาแท่งเหล็กร้อนเชื่อมระหว่างน้ำแข็งสองด้าน แล้วอุณหภูมิของแท่งเหล็กจะค่อยๆ ลดลง ในขณะที่ปลายทั้งสองอุณหภูมิคงที่

เราแก้โดยใช้ finite difference approximation แล้วกำหนดระยะทางว่า u = 100sin(pi*x) ซึ่งค่าที่ได้จะมีการ propagate ออกไป

Partitioning

  1. One data item per grid point
  2. Associate one primitive task with each grid point
  3. Two-dimensional domain decomposition

Communication

  1. Identify communication pattern between primitive tasks
  2. Each interior primitive task has three incoming and three outgoing channels

จากนั้นเรายุบ communication ลงมาตามแนวตั้ง แล้ว map ให้ได้ 3 processor

Sequential Execution Time

เวลาที่ใช้ควรจะเท่ากับ m(n-1)t เมื่อ n เป็นจำนวน element, m เป็นจำนวน iteration และ t เป็นเวลาที่ใช้

Parallel Execution Time

เราต้องเพิ่มตัวแปรเข้าไป คือ p (number of processors) และ L (message latency) ทำให้ได้ execution time เป็น

m(t * ceil ((n-1)/p) + 2L)

Parallel Reduction

ก็แตก tree ออกเพื่อสร้าง binomial tree

เพื่อลด communication เราก็กำหนด agglomeration ให้ดี แล้วก็ยุบก้อน agglomerate แต่ละก้อนลงไป

n-body problem

ปัญหาวัตถุจำนวนหนึ่ง มีหลักการทำโดยใช้ gather บนวัตถุแต่ละชิ้นเพื่อขอข้อมูลตำแหน่งของวัตถุที่เหลือมา แต่การกระทำเช่นนี้เป็นปัญหา เพราะทุกวัตถุต้องทำหมด เราจึงมีการกำหนด hypercube ขึ้นมาเพื่อให้เข้าใจได้ง่าย

การทำ hypercube ทำได้โดย partition แล้วแลกข้อมูลกัน เช่น (0,1), (2,3) ก่อน จากนั้นก็ไปแลกกันอีกที ทำให้ได้ข้อมูลทั้งหมดโดยไม่ต้องส่งข้อมูลกระจาย

Scatter

เป็นการกระทำที่ตรงข้ามกับ Gather คือเราต้องการกระจายข้อมูลที่ไม่เหมือนกัน (แต่อยู่ในชุดเดียวกัน) ออกไปในระบบ

สรุป

แบบจำลองงานและช่องทาง

  1. Parallel computation
  1. Set of tasks
  2. Interactions through channels
  1. Good designs
  1. Maximize local computations
  2. Minimize communications
  3. Scale up

ขั้นตอนการออกแบบ

  1. Partition computation
  2. Agglomerate tasks
  3. Map tasks to processors
  4. Goals
  1. Maximize processor utilization
  2. Minimize inter-processor communication

อัลกอริทึมพื้นฐานที่เรียน

  1. Reduction
  2. Gather and scatter
  3. All-gather

Lecture 4: Message-Passing Programming

Message-passing Model

อธิบายโครงสร้างแบบขนานโดยให้แต่ละ processor มีหน่วยความจำเป็นของตัวเอง ติดต่อกันด้วย interconnection ซึ่ง MPI จะ model ว่าแต่ละ processor อยู่แยกกัน เราไม่ใช้ shared memory เพราะยุ่งยากกว่า

การสื่อสารมีสามแบบคือ one-to-one, one-to-all, และ all-to-one นอกจากนี้ยังมี one-to-all personalized และ all-to-one personalized ด้วย ซึ่งข้อมูลอาจไม่เหมือนกันก็ได้

Processes

เรากำหนดจำนวน process ตอนรัน และต้องคงที่ตลอดการทำงาน ซึ่งสอดคล้องกับแนวคิดของ supercomputer โดยทุกๆ โปรเซสทำงานเหมือนกัน แต่มี ID ต่างกัน ส่งข้อความสื่อสารกันไปมา

ข้อดี

  1. โปรแกรมเมอร์เห็นโครงสร้างข้อมูลดีกว่า
  2. Portable
  3. สร้างโปรแกรม deterministic ได้ง่ายกว่า
  4. Debug ง่าย พ่อง

ข้อเสีย

  1. debugger ไม่เก่งมากพอ
  2. programming เขียนได้ยากกว่า

Problem: Circuit Satisfiability

เป็นปัญหา NP-complete ที่แก้ในเวลา poly ไม่ได้ จึงต้องหาทุกวิธี เนื่องจากในตัวอย่างให้มา 16 input ก็เท่ากับว่ามี 65536 combinations ด้วย การจะไล่ทดสอบทุกๆ input ไม่สะดวก เราจึงแบ่งปัญหานี้เป็นชิ้นย่อยๆ คือตัดวงจรเป็นส่วนๆ แล้วค่อยๆ ทำ

ถ้าแบ่งแบบ functional decomposition จะเห็นว่าไม่มีการสื่อสารอะไรระหว่างกันเลย (embarrassingly parallel)

Cyclic (interleaved) allocation

คือการกระจายแบบวน นั่นคือ process ที่ p จะได้งานที่เป็นเศษ p-1 เพื่อให้ได้ load-balance เนื่องจากถ้าแบ่งเป็น block อาจทำให้ load ไม่เท่ากันได้

ด้วยวิธีนี้ P0 มักได้งานมากที่สุด(เศษจากการหาร) แต่ก็ต่างกันไม่เกิน 1 งานเสมอ

หลักการทำงาน

  1. แต่ละ process แบ่งงานแบบ cyclic (ดังที่กล่าวไว้ข้างต้น)
  2. แต่ละ process หาว่าวิธีไหนใช้ได้ก็แสดงออกมา

การเขียนโปรแกรมเบื้องต้น

  1. include<mpi.h> ก่อน
  2. จากนั้น เรียก MPI_Init เพื่อกำหนดว่าโค้ดต่อจากนี้จะเป็นโค้ด MPI ให้เตรียมตัว
  3. เมื่อทำงานจบ ให้ใช้ MPI_Finalize
  1. Communicator เป็นระบบสื่อสารของ MPI โดยปกติเรามี MPI_COMM_WORLD เป็นตัวตั้งต้นที่มีทุกๆ process อยู่
  2. ในการหาจำนวน process สามารถใช้ MPI_Comm_size เพื่อบอกว่าได้มากี่ process ได้ โดยหาจากขนาดของ MPI_COMM_WORLD
  3. ใน MPI ตัวแปรทั้งหมดเป็น local การแก้ค่าตัวแปรจะมีผลแค่ใน process เดียว
  4. ตัวแปรนอกฟังก์ชัน (external variable) เก็บเหมือนกันแต่ไม่ได้แชร์กัน

การทำงานของโปรแกรมเรา ถ้าแต่ละ process มี rank เป็นค่า id และ มีจำนวน p process จะได้

for (i=id; i < 65536; i+=p)

check_circuit(id, i);

โดย check_circuit เป็นฟังก์ชันแบบ sequential

ดังนั้น โปรแกรมรวมของเราทั้งหมดคือ

#include <mpi.h>

#include <stdio.h>

int main (int argc, char *argv[]) {

int i;

int id;

int p;

void check_circuit (int, int); // External function

MPI_Init (&argc, &argv);

MPI_Comm_rank (MPI_COMM_WORLD, &id); // Write this process’s rank

MPI_Comm_size (MPI_COMM_WORLD, &p); // Write number of all processes

for (i = id; i < 65536; i += p)

check_circuit (id, i); // Sequential function

printf (“Process %d is done\n”, id);

fflush (stdout);

MPI_Finalize();

return 0;

}

การคอมไพล์และรันโปรแกรมที่เขียนโดย MPI

ใช้ mpicc ซึ่งใช้งานคล้ายๆ กับ gcc เช่น

mpicc -O -o foo foo.c

หมายถึง คอมไพล์ foo.c เป็น foo (executable) โดยให้ optimize ด้วย

สำหรับการรันให้ใช้ mpirun -np ./foo ก็ได้

การกำหนดโฮสในระบบ

ให้ใส่รายชื่อเครื่องในไฟล์ .mpi_machines ไว้ในโฮมของตัวเอง และใส่รายชื่อเครื่องใน .rhosts ด้วย เพื่อที่จะได้ทำงานผ่านรีโมทได้ด้วย

Program Modification with Reduction

เราต้องการให้โปรแกรมแสดงจำนวนผลลัพธ์ด้วย แต่เนื่องจากเราไม่ได้เก็บจำนวนผลลัพธ์ที่ได้จากแต่ละ process เราก็ต้องหาโดยการนับ นอกจากนี้จำนวนดังกล่าวก็อยู่บน process ของใครของมันด้วย เราก็ต้องใส่ reduction ลงไปในโค้ดด้วย

ในกรณีนี้เราจะใส่โค้ดนี้ลงไป

MPI_Reduce (&count,

&global_count,

1,

MPI_INT,

MPI_SUM,

0,

MPI_COMM_WORLD);

ความหมายคือ

  1. เอาค่าจาก count (ของทุกๆ คน) มาเป็นตัวตั้ง
  2. ผลลัพธ์ใส่ใน global_count (ของคนเดียว เพราะเป็นการ reduce)
  3. ทำ reduction 1 ครั้ง
  4. ชนิดตัวแปรคือ INT
  5. ดำเนินการ SUM
  6. นำผลใส่ใน process 0
  7. ใช้กลุ่มโปรเซสจาก MPI_COMM_WORLD (ทุกคน)

More functions!

  1. MPI_Barrier barrier synchronization
  1. เหมาะสำหรับการทำงานที่มีหลายๆ iteration เช่น numerical หรือ learning
  1. MPI_Wtick timer resolution
  2. MPI_Wtime current time

Lecture 4

Sieve of Eratosthenes

Algorithm:

  1. Create list of natural numbers 2 … n
  2. k ← 2
  3. Repeat until k^2>n
  1. Mark all multiples of k (except k)
  2. k ← Smallest unmarked number greater than k
  1. Unmarked numbers are primes

Sources of Parallelism

เราทำงานให้ขนานกันได้ โดยช่วงที่กำลังลูปอยู่ก็เอามาขนานกัน

Parallel Algorithm:

  1. เลือก k
  2. กระจาย array ออกไปให้ช่วยกัน mark

Decomposition Options

  1. Interleaved
  1. หา owner ได้ง่ายมาก โดยใช้การ mod
  2. แม้ว่าจะใช้ได้กับโจทย์ของคราวที่แล้ว แต่คราวนี้ทำให้เกิด imbalance
  1. Block
  1. กระจายโหลดได้ดีสำหรับปัญหานี้
  2. ทำงานค่อนข้างยาก

การจัดการกับเศษเมื่อแบ่งงาน

  1. แบ่งงานเป็น ceil(n/p) หรือ floor(n/p)

วิธีการตัวอย่าง

  1. let r = n mod p
  2. if r = 0, all blocks have same size
  3. else
  1. first r blocks have size ceil(n/p)
  2. remaining p-r blocks have size floor(n/p)

สมมติว่าเรามี n = 110, p = 4 จะได้ n/p = 27.5 ⇒ ceil(n/p) = 28 และ floor(n/p) = 27 โดยมี r = 2

นั่นคือ บล็อกที่ 1-2 จะมีขนาด 28 และบล็อกที่เหลือมีขนาด 27 นั่นคือรวมกันเป็น 28+28+27+27 = 110 ตามต้องการ

สำหรับ index ต่างๆ ก็ดูจากเอกสารได้เลย เช่น

  1. Element แรกที่ทำโดย process i
  1. i * ceil(n/p) + min(i,r)
  1. Element สุดท้ายของ i
  1. (i+1) ceil(n/p) + min(i+1,r) – 1

นอกจากนี้ยังมีอีกหลายวิธีในการแบ่ง แต่ประสบการณ์ของอาจารย์บอกว่ามันไม่ต่างกันมากหรอก เพราะเวลาที่ทำจริงๆ unbalanced load ไม่ค่อยมีผลกระทบมาก

ตัวอย่างการเขียน Block Decomposition Macros

#define BLOCK_LOW(id,p,n) ((id)*(n)/(p))

#define BLOCK_HIGH(id,p,n) (BLOCK_LOW((id)+1,p,n)-1)

#define BLOCK_SIZE(id,p,n) (BLOCK_LOW((id)+1)-BLOCK_LOW(id))

#define BLOCK_OWNER(index,p,n) ((((p)*(index)+1)-1)/(n))

การเขียน Macros จะเป็นการสั่งให้ compiler ทำ find-replace บนโค้ดของเราตาม expression ที่กำหนดให้ ทำให้โปรแกรมของเราทำงานได้เร็วเพราะเราใส่โค้ดดิบลงไป ไม่ใช่ฟังก์ชัน

(เชื่อเถอะ พอเอาเข้าจริงก็ก๊อปไอ้สี่บรรทัดนั่นไปแปะอยู่ดีอะ 555+)

Global vs Local Index

กรณี sequential เราก็ลูปยาว แต่ในกรณี parallel นั่นเราจะต้อง map ระหว่าง local/global index ด้วย โดยการเอา BLOCK_LOW มาบวกเข้าไป

MPI_Bcast

ฟังก์ชันนี้เป็นการกระจายข้อมูลเหมือนๆ กันให้ทุกโหนด โดย

int MPI_Bcast(

void *buffer,

int count,

MPI_Datatype datatype

int root,

MPI_Comm comm)

โดยปกติเราก็ใช้ (ถ้าจำไม่ผิดนะ)

MPI_Bcast(&k, 1, MPI_INT, 0, MPI_COMM_WORLD)

ในการส่งค่า k ไปทุกๆ โหนด

ประมาณเวลาทำงาน

  1. chi = time to mark a cell
  2. Sequential exec. time = chi * n ln ln n
  3. Number of bcasts = sqrt(n) / ln sqrt(n)
  4. Bcast time: lambda ceil(log p)

รวมกันโดย

  1. เวลา runtime ลดลงตาม p จะได้
  1. Runtime = chi * n ln ln n / p
  1. เวลาในการสื่อสารที่เพิ่มขึ้น
  1. Comm time = sqrt(n) / ln sqrt(n) * lambda ceil(log p)

ก็เอาสองส่วนมาบวกกัน

การปรับปรุง

  1. เอาเลขคู่ทิ้งไป (ยกเว้นสอง)
  2. แต่ละ process หา sieving prime เองได้ ลดการ bcast ลง
  3. การจัดลูปสามารถเพิ่ม cache hit rate ได้

assignment (?)

ทำ mini project อะไรก็ได้โดยเขียนเป็น parallel

ถ้าสิ้นคิดลองหาจากหนังสือ parallel algorithm

ปัญหาที่น่าสนใจ

  1. traveling salesman
  2. image processing
  3. rendering
  4. simulate หุ้น
  5. fluidization

Lecture 5 (?): Chapter 6: Floyd’s Algorithm

Trend of supercomputer

power efficiency เพราะว่า supercomputer กินไฟมาก มนุษย์หาพลังงานมาให้มันกินไม่ไหว

หัวข้อ

  1. การสร้างอาร์เรย์สองมิติ
  2. แนวคิดเรื่องของขนาดความละเอียด
  3. การสื่อสารแบบ point-to-point
  4. การอ่านและพิมพ์เมทริกซ์สองมิติ
  5. ฯลฯ

All-pairs Shortest Path Problem

คือการหาระยะทางที่สั่นที่สุดสำหรับโหนดทุกๆ คู่ในกราฟ เวลาที่เราทำงานกับกราฟเราสามารถสร้างเป็น adjacency matrix เพื่อเก็บค่าระยะทางได้

  1. adj. matrix เหมาะสำหรับ dense graph
  2. adj. list เหมาะสำหรับ sparse graph

Floyd’s Algorithm

for k ← 0 to n-1

for i ← 0 to n-1

for j ← 0 to n-1

a[i,j] ← min (a[i,j], a[i,k] + a[k,j])

endfor

endfor

endfor

Dynamic Array Creation

เราสามารถใช้ pointer ในการทำงานกับอาร์เรย์เพื่อให้ได้ dynamic array ที่มีขนาดเท่าที่เราต้องการได้ โดยการใช้ pointer นี้จะทำให้เราสามารถจัดโครงสร้างข้อมูลให้เป็นอาร์เรย์เองได้

ในกรณีนี้ เราให้ Bstorage ชี้ไปที่หัวของข้อมูลทั้งก้อน แล้วให้ B ชี้ไปยังอาร์เรย์ (dynamic เช่นกัน) ที่แต่ละช่องชี้ไปยังแต่ละ interval เท่าๆ กันอีกที เอาเป็นว่าดูรูปดีกว่า

ข้อดีของระบบนี้คือประหยัดหน่วยความจำ ถ้าเราใช้ static array เราจะต้องจองที่ไว้เยอะแต่แรก ซึ่งเปล่าประโยชน์

What kind of decomposition?

จากโค้ด เราจะเห็นว่ามีฟังก์ชันเดียวที่มีการเปลี่ยนข้อมูลไปเรื่อยๆ จะทำให้เราใช้ domain decomposition ได้ดีกว่า โดย

(a) คือข้อมูลเดิม

(b) คือการทำงานเวลาที่เราต้องการ update ค่าที่ a[3,4]

(c) ณ iteration ที่ k แต่ละโหนดในแถว k จะมีการ bcast ในคอลัมน์

(d) ณ iteration ที่ k แต่ละโหนดในคอลัมน์ k จะมีการ bcast ใน row

Agglomeration and Mapping

  1. Number of tasks: static
  2. Communication: Structured (แสดงในภาพ)
  3. Computation time per task: Constant (ฟังก์ชันใช้เวลาคงที่)
  4. Strategy: ลดการสื่อสารให้มากที่สุด และสร้าง 1 MPI Task per process

เราสามารถแบ่งข้อมูลที่จะทำออกมาได้สองแบบ คือตามแถว (a) หรือคอลัมน์ (b)

ซึ่งในแบบ a การ bcast ใน row จะหายไป ในขณะที่แบบ b การ bcast ในคอลัมน์จะหายไป แต่เนื่องจากการอ้างอินเด็กซ์ในเมทริกซ์ตามแถวจะง่ายกว่าตามคอลัมน์

การรับค่าจากไฟล์

ปัญหาของ parallel คือการอ่านค่าจากไฟล์ เราจะเอาข้อมูลไปคำนวณยังไงดี

  1. shared file: เปิดจาก central storage แล้วแบ่งไฟล์ตามขนาด
  2. หรือจะส่งไฟล์ไปแล้วให้ไปกระจายทีหลัง

การจะตอบคำถามนี้ได้ก็ต้องรู้ว่า overhead ของแต่ละวิธีมีเท่าไหร่ คำตอบคือทั้งสองวิธีมี overhead หมด แต่วิธีแรกไปหนักที่ NFS Overhead ซึ่งมากกว่า MPI Overhead ในแบบที่สอง

อย่างไรก็ตาม การอ่านแบบที่สองจะมี delay time มากกว่า ถ้าต่างคนต่างรับข้อมูลก็ให้ใครที่ได้ข้อมูลไปแล้วรันไปเลยก็ได้ ซึ่งจะนำไปสู่การทำให้ P1 รันข้อมูลเยอะๆ ก็ได้

Communication

MPI_Send

int MPI_Send (

void *message,

int count,

MPI_Datatype datatype,

int dest,

int tag,

MPI_Comm comm

)

Tag เป็นระบบควบคุมข้อมูลได้

MPI_Recv

int MPI_Recv (

void *message,

int count,

MPI_Datatype datatype,

int source,

int tag,

MPI_Comm comm,

MPI_Status *status

)

Buffer size ของ recv side จะต้องมากกว่า tx side เสมอ

การใช้ Send/Recv

if (ID == j) {

Receive from I

}

if (ID == i) {

Send to j

}

เหตุที่ต้องเอา recv ไว้ก่อน send เพราะ recv ปุ๊บมันจะ block ก็จริง แต่ก็ block เฉพาะ node j เท่านั้น ส่วน node i จะข้าม receive block ไป แล้วไปทำ send เลย

Rendezvous

การทำ send/recv จะทำให้เกิด synchronization ไปในตัว เนื่องจากการ send และ recv จะเสร็จพร้อมกันไปด้วย

สำหรับคำสั่ง isend กับ irecv จะไม่มี sync มาดัก ซึ่งจะช่วยให้ทำความเร็วได้สูงขึ้นในบางกรณี เช่น ติด I/O

Return from MPI_Send/Recv

ฟังก์ชันนี้จะติด blocking จนกว่า buffer จะว่าง ซึ่งจะเป็นเช่นนั้นเมื่อ

  1. ข้อความลง system buffer
  2. ข้อความถูกส่งไปแล้ว

ในอีกมุมหนึ่ง Recv จะรอจนกว่าข้อความจะเข้ามาในบัฟเฟอร์ ซึ่งถ้าข้อความไม่มา ฟังก์ชันจะค้าง

Deadlocks

Send/Recv เกิด deadlocks ได้ง่ายมาก เช่น มีแต่โปรเซสที่ receive ก่อน send บ้าง tag ไม่ตรงกันบ้าง หรือส่งไปผิดโปรเซสบ้าง เป็นต้น

Complexity of this program

Computation

ลูปชั้นในมี complexity (n)

ลูปชั้นกลางถูกรันไม่เกิน ceil(n/p) ครั้ง

ลูปนอกรัน n ครั้ง

จะได้ overall complexity n^3/p

Communication

ลูปในและลูปกลางไม่มีการสื่อสารใดๆ

ในลูปนอกมี broadcast ซึ่งมี complexity = n log p

Overall

ดังนั้น เราเอามาบวกกัน

เนื่องจากเราสามารถทำงานแบบ overlap กันได้ ดังภาพต่อไป

เราอาจเขียนเวลาใหม่ได้เป็น

Lecture 5.5: Performance and Lim’n. of Para. Comp.

Performance

ขึ้นกับอะไรหลายๆ อย่าง เช่น

  1. Parallelism
  2. I/O Requirement
  3. Communication
  4. Runtime เป็นการวัดที่เห็นผลสุด
  1. Sequential Runtime (Ts) เวลาเมื่อรัน sequential
  2. Parrallel Runtime (Tp)
  3. Speed-up หาได้จาก S = Ts/Tp (Perfect Speedup S = P)
  4. วัดจากเวลาที่โปรแกรมแรกทำงานจนโปรแกรมทั้งหมดทำงานเสร็จ
  5. Superlinear Speed-up คือการที่ได้ S มากกว่า perfect speedup อาจเกิดจากความช้าอย่างยิ่งของ sequential
  1. Efficiency
  1. วัดว่าระบบทำงานได้เต็มที่แค่ไหน
  2. E = S / P (หรือ S = EP)
  3. ดังนั้น ในสภาพ perfect จะได้ S = P ⇒ E = 1

Limitation

Code ที่ parallelize ไม่ได้บ้าง I/O ้าง อะไรบ้าง

Amdahl’s Law

สำหรับปัญหาขนาดคงที่ performance ของ parallel program จะถูกจำกัดด้วยส่วน sequential

เช่น หาก s = อัตราส่วนของ sequential code และมี p processors ถ้าเราไม่สนใจ overhead อื่นๆ จะได้

Speedup = 1 / (s + ((1-s)/p))

Overcome Amdahl’s Law

ปัญหา fixed-time

ถ้าเรามี parallel หลายๆ อัน เอาไปรันบนอันเดียวกัน จะทำให้ส่วน parallel ไปรวมกัน ในขณะที่ส่วน sequential เท่าเดิม ทำให้

S = (sTp + (1-s) PTp) / Tp

S = s + (1-s)P

Comm. Overhead

ในการพิจารณาการสื่อสาร เราจะถือว่าโปรแกรมเป็น fully parallel หมด กำหนดให้

W = computational work

T0(W,P) = Comm. overhead func.

จาก

S = Ts/Tp

Tp = Ts/P + T0(W,P)

จะได้

S = 1 / (1/p + T0(W,P)/Ts)

ซึ่งตรงนี้จะทำให้ได้ speedup สูงสุดที่จุดๆ เดียว

การหา communication overhead ทำได้โดยการเทียบให้ dTp/dP = 0 จัดเทอมแล้วจะได้เป็น

P_Opt = sqrt(Ts/(dT0(W,P)/dP))

Simple Machine Model

ในการสื่อสาร เราบอกว่ามีสองส่วน คือเวลาที่จะเริ่มการสื่อสาร และเวลาที่ใช้ในการสื่อสาร

Tcomm = Ts + mTc

เมื่อ Ts = message start-up time, Tc = Comm. time per unit data, m = message size ดังนั้น ถ้าเป็นข้อความสั้นจะเสียที่ Ts มาก ในขณะที่ข้อความยาวจะติดที่ mTc มาก

หากให้ Ts = WTexe (Texe = execution time) จะได้ T0(W,P) = m(W,P) Tc

P = sqrt(WTexe / (dm(W,P)/dP * Tc))

การบ้าน:

นำโปรแกรมของวันนี้ไปรันใน Maeka แล้วหา Texe, Tc

หา per-byte communication time

Matrix Multiplication

กรณีที่ต้องการทำ A x B

ทำได้โดยการ bcast B ไปทั้งหมด แล้วฉีก A เป็นคอลัมน์ไป

จากการวิเคราะห์ B ไปยัง P processor จะได้เวลาแรก T1 = Pn^2Tc เพราะเป็นการส่ง P ครั้ง ครั้งละ n^2

ในการส่งคอลัมน์จะใช้เวลาอีก T2 = P n^2/P Tc = n^2Tc

ในการคำนวณพร้อมกันจะใช้เวลา T3 = n^3 Texe / P

และมีเวลาในการ collect and save อีก (จดไม่ทัน)

Communication function m(W,P)Tc = T1+T2+T4 = (P+2)n^2 Tc

Parallel runtime Tp = n^3/p Texe + (P+2) n^2 Tc

จำนวน processor ที่ควรใช้หาได้จากการหาอนุพันธ์

Max. Speedup หาได้จากการ simplify สมการของ S จะได้ผลลัพธ์เป็น 1/2 sqrt(nG)

สรุปคือ Smax = 1/2 sqrt(nG)

P = sqrt(nG)

ดังนั้น max speedup ขึ้นอยู่กับ

  1. ขนาดปัญหา
  2. machine parameter G = Texe/Tc
  1. ถ้า network เร็ว จะทำให้ Tc ต่ำ speedup จะเพิ่มขึ้น
  2. เอา CPU ห่วยๆ(Intel) มาทำงานแทน Texe จะได้เพิ่มขึ้น – -” กิมลี่เหยียดค่ายมาแต่ไกล

Midterm Exam

ออกตั้งแต่บทที่ 1, 3-6 และเรื่อง performance นี้

1-7 แต่ 2 ไม่ออก

อาทิตย์หน้าไม่เรียน เจออีกทีสอบเลย

อาจารย์จะส่งสไลด์ให้อีกที

Lecture 6: Performance (Cont.)

Scalability

คือการถามว่า performance จะเพิ่มตามจำนวนเครื่องได้มากแค่ไหน เรา model parallel processing time ด้วยสูตร

(ที่ไม่เหมือนที่เราทำตอนแรก)

จะได้ว่า

แตกประเด็นนิดหน่อย

ซึ่งจากข้อจำกัดเรื่่องการสื่อสารนี้ ทำให้ GigabitEthernet ทำ efficiency ได้แค่ 60% (InfiniBand ได้ 80%)

tofu ของ fujitsu (คุยว่า) ทำได้ 90% !!!

การทำงานในสายเคมีนั้นต่างออกไป เพราะงานเป็น batch processing เป็นส่วนใหญ่ ทำให้ไม่ประสบปัญหาด้านการสื่อสาร

ในการวัดประสิทธิภาพ เช่น โดย Top500 จะมีการใช้ค่าต่างๆ เช่น

RPeak คือ performance แต่ละโหนด คูณจำนวนโหนดตรงๆ

RMax คือ sustainable run

ดังนั้น เราบอกได้อีกนัยหนึ่งว่า E = RMax/RPeak

โดยโปรแกรมประเภท MPI ที่มีการสื่อสารกัน จะได้ค่า RMax เพราะมีการสื่อสารกันด้วย ในขณะที่งานกลุ่ม batch ก็จะเป็น RPeak ซึ่งได้ efficiency สูงมาก

Isoefficiency

เราบอกว่า scalability เท่ากับการรักษา efficiency ไว้ได้ นั่นคือ จาก

เมื่อเราเพิ่ม P เราก็ต้องเพิ่ม Ts ด้วยเพื่อกดให้มันคงที เราก็จะย้ายเพื่อหา Ts แทน แล้วกำหนดให้ K = E/(1-E) จะได้เป็น

นั่นคือ เราบอกว่า Ts จะต้องโตขึ้นตาม To ไปด้วยเพื่อรักษา efficiency เอาไว้ให้ได้

เช่น เราบอกว่า

Matrix Multiplication

จาก

จะได้

ถ้าเราให้ E = 0.8 จะได้ K = 0.8/(1-0.8) = 4 แล้วแทนค่า K กลับลงไปในนี้ จะได้

นั่นคือ งานของเราจะต้อง scale ตาม P2

Computational Complexity of Algorithms

โดยปกติเราจะดูตามอัตราการโตของมัน แล้วอธิบายออกมาเป็น O ต่างๆ เช่น O(n2) เป็นต้น ซึ่งหมายความว่า แม้แต่ปัญหา NP ก็คำนวณได้ง่ายถ้าหากมีขนาด input เล็กพอ

แต่ การทำ analysis เราไม่ได้คิดความแตกต่างระหว่างการทำงานแบบ sequential กับแบบ parallel ไว้

Message Passing ทำงานบน shared memory ได้ดี จึงเป็นโมเดลที่ general กว่า

Matrix Multiplication (again)

เราบอกว่าคราวที่แล้วเราส่ง matrix แถวหนึ่งของ A และ B ทั้งหมด ไปคำนวณให้ได้ C แถวหนึ่ง

คราวนี้เราเปลี่ยนใหม่ เป็นการส่ง A และ B บางส่วน เพื่อหา C บางส่วน

วิธีนี้เรียกว่า Cannon’s Algorithm (ไม่ใช่ Canon in … อะไรนั่นนะ) ช่วยให้การประมวลผลเพื่อคูณเท่าเดิม แต่ลดการสื่อสารลงอย่างเห็นได้ชัด เพราะว่า หากเรากำหนดให้เป็นการคูณเมทริกซ์ขนาด n*n จะได้ว่า

 

แบบเดิม

Cannon

การกำหนดจำนวน processor

p processors

p^2 processors

(เพื่อให้แบ่งเป็นช่องเท่าๆ กันทั้งแนวตั้งและแนวนอน)

ปริมาณข้อมูลต่อ processor

n*(n/p)+n*n

n*(n/sqrt(p))+n*(n/sqrt(p))

ปริมาณการคำนวณ

2n^3/p

2n^3/p

สรุปการทำงานได้ 3 ขั้น

  1. master ส่ง A, B ไปให้ slave คำนวณ
  2. compute
  3. return answer

การส่งส่วนของตารางไปก็จะใช้เวลา T1 จากนั้นคำนวณโดยใช้เวลา T2 ที่ขึ้นกับ Texe จากนั้นส่งกลับมาด้วยเวลา T3

จะได้ Tp = T1 + T2 + T3 = 2n^2 / sqrt(P) * PTc + n…

วิธีการที่ง่ายคือเรา formulate สมการให้ได้ S = EP ก่อน เราก็จะแยก efficiency ออกมาได้

Parallel Sorting

ขั้นตอนการทำงาน

  1. Master task read data from disk => memory
  2. Master select P-1 Pivot, separate and put into bucket
  3. Each bucket sent to slave
  4. Local sort
  5. Send back

เนื่องจาก sorting ขึ้นกับโครงสร้างของข้อมูล เราวิเคราะห์ได้ยากกว่าพอสมควร

ในกรณีนี้เราจะพูดถึง bucket sort โดยเราทำให้แต่ละ bucket ลงไปอยู่ในแต่ละ process จากนั้นให้แต่ละ slave process ไป sort ของตัวเอง แล้วส่งข้อมูลกลับ ซึ่ง bucket sort นี้ไม่ใช่วิธีที่ดีที่สุด แต่เข้าใจง่ายพอสมควร

Assumptions

  1. บอกว่า sorting and bucket selection ใช้เวลา Texe เท่ากัน ทำให้
  1. Tpar = nTexe + 2nTc + Texe(n/p) log (n/p)
  2. Tseq = nlog(n) Texe
  3. ทำให้ได้ speedup เท่ากับสองอันหารกัน ซึ่งเรา (ควรจะช่างมันดีมั้ย?) จะแยกให้ได้ S = EP
  1. บอกว่า n >> p (n มากกว่า p มากๆ ไม่ใช่ n shift right p bits)

Analysis

  1. ถ้า G เพิ่ม (อัตราระหว่างการคำนวณต่อการสื่อสาร) จะได้ speedup มากขึ้น
  2. n เพิ่ม speedup เพิ่มเล็กน้อย
  3. ถ้า P เพิ่ม เป็นไปได้ว่าเวลาทำงานจะน้อยลง แต่ E ก็ลดลงด้วย
  4. speedup ลด eff จะ lost เพราะสู้ overhead ไม่ไหว

Network สำคัญมากสำหรับ cluster เพื่อลด overhead ด้าน communication หรือไม่ก็เอาน้อยเครื่อง แต่ละเครื่องโหดขิงแทน

Internet Service เยอะๆ จะจัดการยังไง

พยายาม classify data ว่ามีอะไรที่แยกเก็บหลายเครื่องได้

dwarven skill – -”

Lecture 6.5: CUDA Workshop

GPU Computing คือ การเอา Graphic Processor มาช่วยในการประมวลผล

ช่วยให้ทำงานเร็วขึ้น ประหยัดพลังงานได้มากกว่าด้วย

performance ได้ใบละ 240 GFlops

nvidia ออกการ์ดรุ่นใหม่ที่ประมวผลได้ 1 TFlops

CUDA is NVIDIA’s parallel computing architecture

Applications

  1. image/video processing
  2. computational biology/chemistry
  3. fluid dynamics simulation
  4. CT image reconstruction
  5. etc.

Installation

  1. Install CUDA driver
  2. Install CUDA SDK
  3. อ่านเพิ่มใน CUDA zone

GPU arch

  1. มี stream multiprocessor (SM) อยู่บนชิป โดยแต่ละตัวมี shared memory ที่ใช้ร่วมกันระหว่าง stream processor (SP) ต่างๆ ที่อยู่ข้างใน
  2. RAM มีสองระดับคือ on-chip กับ off-chip ก็ตามชื่อมัน
  3. การทำงานของมันจะเป็นการรับ input เข้ามาแล้วกระจายงานออกไปยัง processor ต่างๆ

Programming for CUDA

CUDA จะแบ่ง node ออกเป็น host (CPU + memory) เป็นส่วนติดต่อกับโลกภายนอกให้ และ device (GPU + memory) จะทำการคำนวณเป็นหลักแทน โดยเขียนเป็นสองส่วน

CUDA รองรับ binding หลายแบบ แต่ปกติจะทำงานกับ C/C++ มากกว่า โดย NVCC จะแยกส่วนโค้ดให้เรา แยกคอมไพล์ แต่ link เข้าด้วยกัน

ของที่วิ่งได้มี 3 แบบ พิจารณาเป็น layer ดังนี้

  1. Grid = card 1 ใบ มีหลาย block
  2. Block = core ใน CPU โดย 1 อันมีหลาย thread
  3. thread เบากว่าของ CPU มาก ใช้เวลาน้อยกว่ามากเช่นกัน
  1. มีโครงสร้างเป็น 2 มิติได้

(เราจะไม่พูดถึงการทำงานในระดับฮาร์ดแวร์โดยตรงเพื่อรักษา portability)

CUDA ทำงานด้วย GPU ซึ่งทำงานได้ไม่เยอะมาก แต่เนื่องจากมีจำนวนมากจึงทำงานได้รวดเร็ว ซึ่งแน่นอนว่าเฉพาะอัลกอริทึมในกลุ่ม SIMD (single instruction, multiple data แปลไทยว่างานน้อยข้อมูลเยอะก็ได้) เท่านั้นที่เอามาทำงานบนนี้ได้ดี

ข้อดีของการจัดแบ่ง block คือ ระบบ runtime จะทำให้เราเองเวลาที่เรามี GPU แบบต่างๆ กันออกไป ทำให้เกิด flexibility ได้มากกว่า

ในการทำงานจริง เวลาทำงานจะมี thread id, block id, block dim, grid dim เป็นตัวแปรที่จะบอกขนาดระบบของเรา และโปรแกรมก็จะทำงานเป็นขั้นๆ

  1. จอง device mem ก่อน
  2. โยน input เข้า device mem
  3. call CUDA kernel เพื่อเริ่มทำการ Compute (kernel function)
  4. ส่ง output กลับมาใน host mem
  5. คืนหน่วยความจำ

แต่การส่งข้อมูลไปมาจะใช้เวลามาก โดยค่าย AMD ใช้ OpenCL บน Fusion แทน (Fusion ลดระยะทางระหว่าง CPU-GPU ได้)

Asynchronous Launch

เป็นการสั่งให้ทำงานไปก่อนแล้วทำอย่างอื่นรอไปด้วยได้ จึงไม่จำเป็นที่ CPU จะต้องรอ GPU

Lecture 7: GPU Programming

ตัวอย่างพื้นฐาน: การบวกเลขสองตัว

การบวกเลขจะทำได้ต้องมีการกำหนดหน่วยความจำบน CUDA โดยใช้

  1. cudaMalloc() เป็นการจองพื้นที่
  2. cudaMemcpy() เป็นการลอกหน่วยความจำ เช่น ระหว่าง device กับ host
  3. cudaFree() เป็นการคืนพื้นที่หน่วยความจำ

ในการเขียน CUDA เราจะเขียนโค้ดชุดเดียว และโดยปกติเราจะเอา dev_ ไว้ข้างหน้าตัวแปรฝั่ง device [a]เช่น *dev_a สำหรับตัวแปร a เป็นต้น

Kernel Code

  1. Standard C
  2. ใช้ standard math library ได้ เช่น math.h
  3. can’t use ยกเว้นอยู่บน fermi
  1. stdio.h >>> หมายความว่าทำ I/O แบบปกติไม่ได้เลย
  2. stdlib.h

Kernel Call Syntax

  1. blocks per grid/threads per block

Function Type Qualifiers

ฟังก์ชันแต่ละชนิดอาจถูกเรียกได้เฉพาะในการ์ดเท่านั้น เป็นต้น เราจึงใช้ type qualifier ในการกำหนดว่าใครเรียกอะไรได้

Builtins

  1. Hardware Registers
  1. threadIdx (thread index)
  1. .x, .y, .z
  1. blockDim (block dimension)
  1. คือจำนวน thread ในแต่ละ dimension
  2. .x, .y, .z
  1. blockIdx (block index)
  1. .x, .y
  1. gridDim (grid dimension)
  1. คือจำนวน block ในแต่ละ dimension

จากภาพ จะเห็นว่าการหา global index ของแต่ละ thread ทำได้โดย

k = blockIdx.x * blockDim.x + threadIdx.x

เช่น thread สีแดงในภาพจะมี k = 2 * 4 + 1 = 9

Compiling CUDA stuff

ไฟล์ kernel จะเป็น .cu (ไม่ใช่จุฬา) แล้วใช้ nvcc ในการคอมไพล์ จากนั้นจะรันได้ตามปกติ

Optimization

Memory Hierarchy

Warp

Warp คือการทำงานเป็นรอบๆ ของ GPU โดยฮาร์ดแวร์จะรันครั้งละ 1 Warp เท่านั้น

การใช้หน่วยความจำ

// (i,j) = ตำแหน่งของ thread

__shared__ int temp[16][16];

int j = blockIdx.x * blockDim.x + threadIdx.x

int i = blockIdx.y * blockDim.y + threadIdx.y

temp[i][j] = array_global[i][j];

__syncthreads();

// …

Performance Model. <<< กุว่าออกสอบ ชัวร์สัสๆๆๆๆๆๆ

จาก

Ts = W

delta = m_output / m

overhead = m/B + dm/B

Tp = s*Ts + (1-s)Ts/P + overhead

S = Ts/Tp = E*P

S = Ts / [ sTs + [ (1-s)Ts/P ] + overhead ]

Assumption

1.ignore scheduling

2.S=>0

S = Ts/[Ts/P + m(1+d)/B]

S=E*P

S=[Ts/ [Ts + (mP(1+d)/B) ] ] * P

S=(1/(1+ [ [mP(1+d) ] / (Ts*B) ] ) ) * P

พิจารณาจาก m/Ts ถ้าน้อยมากๆ คือ ขนาดข้อมูลจะน้อยมากถ้าเทียบกับ Bandwidth

optimize >> เพิ่ม max Bandwidth

d น้อยมากจนแทบไร้ความหมาย เป็น parameter ที่ขึ้นกับ algorithm

hardware parameter ได้แก่ bandwidth

algo ที่ favour CPU >>> need workload เยอะๆ คำนวณเยอะๆ ส่งค่ากลับมาน้อยๆ

ถ้าดูแบบลวกๆ ก็ดูแค่ m/Ts พอ

Design

  1. ออกแบบว่า โมเดลการคำนวณเป็นยังไง RAM >> VRAM >> CUDA >> RAM
  2. Transform to Math Formula : Tp = s*Ts + (1-s)Ts/P + M/B + dM/B
  3. หา Speed UP : S = Ts/Tp
  4. แทนค่า แล้วตัดตัวแปร เพื่อ Simplify แล้ว หา Term เพื่อเพิ่ม Performance
  5. B1 = alpha*B โดย alpha >>1 delta <<1
  6. หาว่า S เพิ่มเท่าไหร่
  7. เอา alpha ไปเติมหน้า Ts แล้วจัดสูตรเอง >>S=(1/(1+ [ [mP(1+d) ] / (Ts*B) ] ) ) * P

การบ้าน

เขียนงาน Travelling Salesman Problem on MPI & GPU โดยเอากราฟมาแตก instance กระจายไปหลายๆ โหนด โดยให้มี master แตก subgraph เช่น เรามี 8 node ก็แตกได้เป็น 8 subgraph แล้วรันด้วย GPU แล้วให้รันเทียบกันโดยใช้ input เดียวกัน

ควรเขียนเป็น sequential ก่อน เพื่อที่จะได้หา speedup ได้ แต่ pitfall คือการใช้เวลาบน sequential อย่างน้อย 10-20 เท่า ดังนั้น หาก GPU ใช้เวลา 1 ชั่วโมง ถ้าทำ sequential อาจใช้เวลาทั้งวัน

Lecture 8: Chapter 2

SISD, SIMD, MISD, MIMD

SISD หรือ Single Instruction, Single Data เช่น PC ธรรมดาสามัญ

SIMD คือ Single Instruction Multiple Data เช่น GPU หรือ Pipeline

MISD หรือ Multiple Instruction Single Data เช่น systolic array เป็นกลุ่มของ processor ที่รับข้อมูลอันเดียวแล้วไหลไปตาม instruction ต่างๆ ข้อดีหนึ่งของ Systolic Array คือการใช้งานแบนด์วิธที่ดีมากจาก local communication แต่เขียนโปรแกรมได้ยาก เพราะมีทั้ง space scheduling และ time scheduling ทำให้ไม่ค่อยเป็นที่นิยม

ตัวอย่าง systolic array (อันนี้แบบ MIMD)

MIMD หรือ Multiple Instruction Multiple Data

Interconnection Networks

Interconnection ถูกใช้เพื่อ

  1. เชื่อม processor <-> memory
  2. เชื่อม processor <-> processor

มีสองลักษณะหลักๆ

  1. shared มีลักษณะเป็น (Bus)
  1. decentralized
  2. ส่งได้ทีละข้อความ
  1. switched (เหมือนเน็ตเวิร์ครึเปล่า สุดท้าย Switch ก็ดีกว่า Hub หมดทุกด้าน)
  1. point-to-point
  2. ส่งได้พร้อมกันหลายคน
  3. Scalable

Switched Topology

Switched มีเป็น topology อีก โดยเราให้ V เป็น processor และ E เป็น comm. path เราแบ่งได้เป็น

  1. Direct
  1. Ratio ของ switch node : processor node = 1 : 1
  2. ทุกๆ switch node ต่อไปยัง 1 processor node และ 1 (or more) switch node
  1. Indirect (เหมือน Hierarchy Design ของ CCNA 3-1 เลย)
  1. มี switch ที่ต่อกันเอง อาจเป็น multi-tiered แบบที่เรียนใน CCNA ESwitching

Evaluation

  1. Diameter
  2. Bisection width
  3. Number of edges / node
  4. Constant edge length? (yes/no)

2D Mesh (not 2D Anime Girl)

เป็นการวาง node ให้มีลักษณะเป็นตารางๆ เป็นรูปแบบที่ดีในเรื่องของ scalability แต่ปวดหัวเรื่อง routing โคตรๆ และใช้การ์ด 4 port ด้วย ก็เลยมึนๆ

(a) เป็น 2d grid ธรรมดา ส่วน (b) เป็นแบบ wrap-around ซึ่งจะลดขนาดลงเหลือครึ่งเดียว เช่นในภาพ ระยะทางจะลดลงจาก 3 เหลือ 1.5

  1. Diameter: Q(n1/2)
  2. Bisection width: Q(n1/2)
  3. Number of edges per switch: 4
  4. Constant edge length? Yes

Binary Tree

ข้อดีคือ local traffic จัดการได้ดีมาก แต่ global traffic จะใช้เวลานานขึ้นมาก เหมาะกับอัลกอริทึมบางอย่างเช่น divide and conquer เพราะสอดคล้องกับรูปแบบของอัลกอริทึม ดังนั้น binary tree network จะเหมาะกับกิจกรรมเช่น fast Fourier transform

  1. n = 2d processor nodes, n-1 switches
  2. Diameter: 2 log n
  3. Bisection width: 1
  4. Edges / node: 3
  5. Constant edge length? No

Hypertree Network

เป็นการเพิ่มจำนวนเส้นทางให้กับแต่ละโหนด โดยเราเอา (a) ผสมกับ (b) ได้ ©

  1. Diameter: log n
  2. Bisection width: n / 2
  3. Edges / node: 6
  4. Constant edge length? No

Butterfly Network

ออกแบบมาเพื่อทำ divide and conquer โดยเฉพาะ เหมือน FFT ที่เราเคยทำ ใช้ bit address

Hypercube

การสร้าง hypercube ทำจาก 2 อันมาต่อกันแล้ว double ไปเรื่อยๆ

หากสังเกต Hypercube ที่ได้ จะพบว่า การเดินจากโหนดหนึ่งไปยังโหนดข้างเคียงจะมีการเปลี่ยน address เพียงบิตเดียว กล่าวคือ ระยะห่างระหว่างโหนดคู่ใดๆ หาได้จากจำนวนบิตที่ต่างกันของ address

Hypercube สเกลได้ไม่มาก แต่มีข้อดีตรงที่สามารถ embed mesh/tree algorithm ลงไปได้พอดี ทำให้ใช้งานกับ fluid dynamics

  1. Diameter: log n
  2. Bisection width: n / 2
  3. Edges per node: log n
  4. Constant edge length? No

Other Types

  1. Vector processor ทำงานโดยมีคำสั่งสำหรับ vector ด้วย นอกเหนือจากจำนวน scalar ปกติ
  2. Processor array มี processing element, memory และ interconnect ด้วย เช่น GPU
  1. ทำงาน parallel ได้ดี แต่มีข้อจำกัดบ้าง เช่น multi-user ไม่ค่อยได้ ไม่ค่อยเหมาะกับ conditionals เป็นต้น
  1. Multiprocessor เป็น multiple-CPU computer with shared memory

Lecture 9

  1. Centralized Multiprocessor เป็นการขยายระบบ uniprocessor ออกมา โดยเพิ่ม CPU ลงไปบนบัส แล้วให้ processor ทั้งหมดเท่ากัน คือใช้ RAM ด้วยกัน ทำให้มีเวลาเข้าถึงหน่วยความจำเท่ากันทุก CPU นั่นคือ
  1. Uniform Memory Access (UMA)
  2. Symmetrical multiprocessor (SMP) — ทุกตัวทำงานเหมือนกัน
  1. Asymmetrical MP มาจากการแยกบทบาทกัน

ปัญหาของการแชร์หน่วยความจำ

  1. Cache Coherence
  1. แคชจะ serialize งานให้เราได้ก็จริง แต่เราจะแน่ใจได้อย่างไรว่าถ้า CPU สองตัวเรียก address เดียวกัน จะได้ค่าเดียวกันออกมา โดยเฉพาะเวลาที่มีใครแก้ค่าในแคชตัวเองแล้วเขียนค่ากลับลงไปในหน่วยความจำ
  1. Synchronization
  1. Mutual exclusion
  2. Barrier

Write Invalidate Protocol

เมื่อเกิดการ write ข้อมูลไม่ว่าจะจากใครก็ตาม จะบังคับให้ invalidate ค่าออกจาก cache ของ CPU ทุกตัว บังคับให้ fetch ใหม่ทันที ปัญหาคือไปลดประโยชน์ของ cache ลง ทำให้เสีย performance ไป แถมยังต้องคอยมองในบัสด้วยว่าต้องล้างค่าหรือไม่ นอกจากนี้ยังใช้กับ distributed MP ไม่ได้ด้วย

Distributed Multiprocessor

เป็นการกระจายหน่วยความจำออกไป ทำให้สเกลได้ดี เรียกอีกอย่างว่า Non-Uniform Memory Access (NUMA) MP

[Not this NUMA: http://www.youtube.com/watch?v=60og9gwKh1o]

ซ้าย: UMA, ขวา: NUMA

ปัญหาคือพวก NUMA มันไม่ค่อย support ในฮาร์ดแวร์เท่าไหร่ implement ก็ยาก เพราะไม่มี shared memory ให้อ่านได้ง่ายๆ เลยต้องมาทำโปรโตคอลอีกตัว

Directory-based protocol

เป็นการเก็บข้อมูลหน่วยความจำเอาไว้ ว่ามีการแชร์ข้อมูลกันอย่างไรบ้าง โดยมีสามสถานะ

  1. Uncached = ไม่มีใครใช้อยู่
  2. Shared = อ่านอย่างเดียวเพราะใช้หลายคน
  3. Exclusive = เขียนได้ ใช้เองคนเดียว

กระบวนการอ่านทำไม่ยาก แต่ในการเขียนจะต้องให้เจ้าของหน่วยความจำล็อก exclusive แล้ว invalidate คนอื่นทั้งหมดด้วยจึงจะเขียนได้ ลองดูสไลด์เพื่อความเข้าใจ

แต่สุดท้ายเมื่อผู้ถือบล็อกใช้งานเสร็จแล้วก็จะต้อง write back แล้วคืนจาก exclusive กลับลงมาเป็น uncached เหมือนเดิมด้วย

Multicomputer

มีแอดเดรสแยกกัน แยกหน่วยความจำกัน คุยกันด้วย message passing เช่นคลัสเตอร์และ MPI โดยแยกเป็น asymmetrical (frontend-backend) ที่ทำ backend ได้ไม่ยากมาก

ฟังดูดี แต่ frontend พังทุกอย่างก็จบ แต่ก็ทำให้จู่โจมเข้ามาได้ยากด้วย อย่างไรก็ตาม การมี frontend เดียวทำให้สั่งงานได้ช้า

ตัวอย่างเช่น HPC Cluster ต่างๆ

Symmetrical MC

มักปรากฏในระบบ cloud ดูแลได้ยากกว่า (ขึ้นกับมิดเดิลแวร์) มักใช้ทำบริการต่างๆ เพราะมองเห็นได้ทุกโหนด นอกจากนี้ยังมี overhead ต่ำกว่าด้วย

Mixed MC

Commodity Cluster

เป็นเครื่อมคอมที่เหมือนๆ กัน เอามาทำงานร่วมกัน บางคนก็เรียกว่า Beowulf ตามชื่อ

Network of Workstations

เป็นเครื่องที่ใช้ทำงานได้ และรัน parallel ลงไปด้วยได้

Lecture 10: Cloud Computing

เทคโนโลยีมันเริ่มมาจาก cluster ถัดมาก็เป็น grid ซึ่งมาจากไอเดียการกระจายงานให้ศูนย์คอมฯ ที่ต่างๆ มาช่วยกันประมวลผล ถัดมาก็เป็น cloud

distro หลักๆ ก็คือ ROCKS

Cloud computing is

  1. a style of computing in which dynamically scalable and often virtualized resources are provided as a service over the internet

ทำไมถึงเปลี่ยน

  1. จุดอ่อนของ grid
  1. network เป็นคอขวด
  1. domain of authority
  1. มีปัญหาเรื่อง site compatibility policy
  1. ประหยัดการใช้พลังงาน
  2. reliability
  1. performance / security
  2. server ตรงกลางจะน่าเชื่อมากกว่า

Cloud Computing definitions

  1. 5 characteristics
  2. 3 models

Cloud Characteristics

มี 5 อย่าง

  1. on-demand self-service
  1. manage resource ตัวเองได้
  1. Broad network access
  1. เข้าถึงจากที่ไหนก็ได้
  1. Resource pooling
  1. ดึงมาใช้ (provision) user ได้
  1. Rapid elasticity
  1. เพิ่มลดกำลังได้ ยืดหดได้ตามการใช้งานจริง
  1. Measured service
  1. มีมิเตอร์เก็บตังค์ วัดการใช้งานได้

Cloud Service Models

Characteristics ทั้งห้าข้อสามารถนำมาสร้างบริการได้สามระดับ

  1. Software as a Service (SaaS)
  1. Web Application
  1. google product ทั้งหลาย เช่น gmail, drive
  1. Platform as a Service (PaaS)
  1. คือการทำ cloud เป็น programming platform
  2. เช่น MS SQL Azure, Google App Engine, Cloud Foundry, Heroku, Appscale
  1. cloud foundry แลดูมีอนาคต?
  1. Infrastructure as a Service (IaaS)
  1. คือการทำ middleware แล้วให้บริการเป็นเครื่องๆ
  2. เช่น Amazon EC2
  3. การ host VM ในสมัยก่อนจะใช้ราคาระหว่าง web hosting กับ colocation

การซื้อบริการแทนที่จะซื้อเครื่อง จะช่วยลดปัญหาการซื้อเครื่องได้ โดยเฉพาะในองค์กรภาครัฐ ที่ค่าใช้สอยเบิกง่ายกว่าครุภัณฑ์

Deployment Model

มี 4 แบบ

  1. Private Cloud
  1. ใช้ในองค์กรเดียว
  1. Community Cloud
  1. ใช้ข้ามองค์กร
  1. Public
  1. ใครใช้ก็ได้
  1. Hybrid
  1. อยู่ข้ามชนิดจากที่บอกไว้ในสามอย่างแรกได้
  2. เป็นความต้องการของหลายๆ องค์กร

(OpenStack ยังไม่มีแนวคิดเรื่อง virtual data center เหมือน vDC ของ VMware ทำให้ต้องมาทำทุกอย่างทีละ VM ถ้ามีแนวคิด vDC จะช่วยให้จัดการงานได้ง่ายขึ้น)

Benefits of Public Cloud

  1. ค่าเครื่องถูกลง no upfront investment
  2. ใช้ได้ตามที่ต้องการ On demand access
  1. เปิดใช้งานได้ง่าย เร็ว
  1. จัดสรรทรัพยากรดี efficient resource allocation
  1. เช่น การ scheduling ต่างๆ
  1. คิดตังค์กันง่ายๆ nice pricing
  1. เช่น ตามการใช้งาน QoS ฯลฯ
  1. เร็วส์ app acceleration
  1. Parallelism ที่ได้สามารถนำมาใช้กับการทำข้อมูลใหญ่ๆ ได้
  1. High Availability, Scalability
  2. 3rd Party Service

Elasticity

ลองนึกภาพระบบขนาดใหญ่ เช่น สรรพากร ที่เวลาเก็บ ภ.ง.ด. จะเก็บเฉพาะมีนาฯ หรือการลงทะเบียนจะทำแค่เทอมละครั้ง ทำให้เรามี capacity เหลืออยู่มากเวลาที่ไม่ใช้ แต่ก็ไม่ค่อยจะพอเวลาที่ต้องใช้เช่นกัน

จำนวนผู้ใช้ Steam ที่ขึ้นๆ ลงๆ

Elasticity จะทำให้เราจัดสรรทรัพยากร “เกินพอดีนิดเดียว” และเพิ่มลดทรัพยากรได้ทันทีที่ต้องการ

Enabling Technology

  1. Cluster and Grid Technology
  1. สร้างระบบขนาดใหญ่ได้ง่าย
  1. Service oriented Architecture
  1. ทำทุกอย่างให้เป็น service ได้
  2. สามารถเอาไปใช้กับงานขนาดใหญ่ได้
  1. Web 2.0

trend?

  1. social
  2. service-based

Cloud Service Provider

  1. Amazon
  1. Amazon Web Service
  1. Google App Engine
  1. PaaS
  2. มาตรฐาน Java/Python API มาหุ้มไว้
  1. Microsoft Azure
  1. Hybrid Cloud
  2. ดึง data ไป process บน cloud แล้วย้ายกลับมาได้
  3. คุยกันผ่าน service bus

โครงที่ run app ได้ มี 2 ประเภท

  1. VM
  2. runtime

Cloud Application and Service

  1. App Development
  1. ต้องแยกตัว data กับ management ออกมาจาก VM
  2. Service-Oriented Architecture (SOA)
  1. Applications
  1. Mobile backend e.g. iCloud, Kindle
  1. เป็น backend ให้ mobile service ต่างๆ
  1. Parallel batch processing
  1. scientific computing
  1. Enterprise analytics
  1. risk analysis, stock market analysis
  1. Desktop extension
  1. office live space

Coexisting Delivery Models

Enterprise + Private Cloud + Public Cloud

สามารถทำงานร่วมกันได้ โดยใช้ hybrid cloud ช่วย

Roadmap to Cloud

  1. Complex Infrastructure
  2. Physical Consolidation เช่น CPE nebula
  3. Virtualization
  4. Cloud

ปัญหา cloud

  1. availability
  1. elasticity สามารถเพื่ม availability เพื่อลดปัญหา DDoS ได้
  2. ใช้ cloud provider มากกว่า 1 ตัว
  1. data lock-in
  1. ยังไม่มี standard
  1. data confidentiality and auditability
  2. data transfer bottlenecks
  1. มันส่งกันไปมาเยอะๆ เลยกิน bandwidth network
  1. performance unpredictability
  1. ควรมีการรับประกันว่าไม่ได้แชร์กับใคร performance ไม่ตก
  1. software licensing

Lecture 10.5+11(?): Intro. to OpenStack

OpenStack เกิดจาก NASA Nebula ร่วมกับ Rackspace เพื่อรองรับ IaaS

โครงสร้างหลัก

มีสามส่วน คือ Compute, Networking และ Storage โดยควบคุมผ่าน Dashboard อีกที ทุกอย่างจะเป็นส่วนแยกๆ กันเป็นก้อนย่อยๆ และต่างฝ่ายจะต่างมี assumption ซึ่งกันและกัน ทำให้เราสามารถปรับการทำงานได้หลากหลาย เช่น อาจให้รันบน KVM หรือ Xen ก็ได้

cloud กับ cluster มีโครงสร้างต่างกันตรงที่

  1. cloud ต้องมี management node คอยควบคุมการทำงานของเครื่องอื่นๆ และมี interface ให้เราใช้ในการสั่งการ โดยเราจะเข้าใช้บริการจากเครื่องไหนก็ได้ ไม่จำเป็นต้องเป็น management node เสมอไป
  2. cluster มี head node, worker node คอขวดอยู่ที่ frontend เพราะเวลาจะ remote เข้ามาก็ต้องผ่าน head node เสมอ แต่มีข้อดีก็คือ security สูง เพราะเข้ามาได้ทางเดียว

โดยปกติ เราจะเรียกเป็น codename ต่างๆ

  1. Horizon = Dashboard
  2. Nova = Compute
  3. Glance = Image เป็นที่โหลด VM มารัน
  4. Keystone = Identity เป็น security server จัดการเรื่อง authentication
  5. Swift = Storage เป็น file server ให้ ปัจจุบันเน้นไปทาง caching file system ซึ่งมองเป็น object ซึ่งอาจมีการใช้ Index เพื่อเพิ่มความเร็วในการ query ไม่ได้มองเป็นโครงสร้างซับซ้อนเหมือนเมื่อก่อน

แบ่งเป็นสองส่วน คือส่วน controller ที่ลง nova-scheduler ไว้ กับส่วน compute ที่ลง nova-compute ไว้ ในตัว controller จะมี queue กับ nova database และ API ที่ใช้ร่วมกับ API อื่นๆ ได้ การเรียก image จะทำผ่าน glance และ security ทำผ่าน keystone

Nova เป็นส่วนที่จะทำงานเกี่ยวกับ compute แต่ใช้ libvirt ในการทำงานกับ VM ทำให้มันทำงานได้ไม่ต่างจาก libvirt มากนัก นอกจากนี้ ทำให้ Nova ทำงานได้บนทุกระบบปฏิบัติการที่ใช้ libvirt ได้ด้วย (แต่ไม่รับประกันว่าจะโยนงานไปมาระหว่างระบบปฏิบัติการที่แตกต่างกันได้หรือไม่)

ทั้งหมดจะติดต่อกันผ่าน message-queue ชื่อ RabbitMQ ซึ่งเป็นแบบ asynchronous mode

Nova Component

  1. เป็น compute infrastructure
  2. แบ่งเป็น
  1. cloud controller
  1. จัดการเรื่อง scheduler
  1. compute node
  1. จัดการ VM และ daemon ต่างๆ ของ node
  1. API Server (nova)
  2. …จดไม่ทัน
  3. Volume Workers (nova-volume)
  1. จัดการเรื่อง storage เช่น LVM
  2. ทำการแยก data ที่เก็บออกจาก OS ที่ launch มากับ VM
  1. Scheduler (nova-scheduler)
  1. map nova-API เพื่อเรียก component ที่เหมาะสม
  2. ปัจจุบันยังทำได้แค่โยนมั่วเฉยๆ
  1. compatible กับ amazon EC2
  2. message ที่ส่งไปมา คุยด้วย JSON
  3. การควบคุม VM (nova-compute)
  1. native
  1. XEN
  2. VMWare
  1. libvirt
  1. KVM
  2. XEN
  3. QEMU
  4. LXC

Storage Infrastructure (Swift)

  1. เก็บข้อมูลเข้าไปแล้วดึงออกมาได้
  1. แต่ยังไม่ถึงขั้น process data
  1. virtual object
  1. Amazon S3
  1. เอาไว้เก็บ object จำนวนมาก
  2. เก็บ object แล้วกระจายตาม node ได้
  3. scale ได้
  4. ประกอบด้วย
  1. Swift Proxy Server เหมือน nova-scheduler
  2. Swift Object Server เก็บ object จริง
  3. Swift Container Server เก็บ index ว่า object นี้อยู่ไหน
  4. Swift Account Server
  5. The Ring

Imaging Service (Glance)

  1. แบ่งเป็น
  1. API server
  1. เอาไว้คุยกับส่วนอื่นๆ
  1. nova-compute
  2. user
  3. keystore
  1. store adapter
  1. เก็บ file system และ storage ต่างๆ เช่น
  1. swift
  2. S3
  3. HTTP
  4. PBD
  5. filesystem
  1. registry server
  1. glance DB
  1. เก็บ image ของ VM ไว้
  2. เชื่อมกับ S3 storage และ switch ได้ ย้ายข้ามค่ายได้
  3. ดึงผ่านเว็บได้

Nova Network

  1. set VPN ระหว่าง network group ให้
  2. การทำ virtual network
  3. ทำให้ VM ที่อยู่คนละ network คุยกันได้

KeyStone

เป็นตัวที่เก็บ identity โดยเรียกผ่าน euca-tools ได้

Dashboard (Horizon)

เป็นส่วนที่จะเป็นภาพให้เห็นสถานะการทำงานต่างๆ ของ OpenStack โดยเป็น GUI

ระบบ Project ของ OpenStack คล้ายกับ vDC ของ VMware

Instance Management

Instance ต่างๆ มีทั้งหมด 6 ขั้นตอน

  1. Scheduling
  2. Networking
  3. Launching
  4. Running
  5. Terminating
  6. Shut Down

โดยเราสามารถจัดการมันได้ด้วย EC2 API หรือ euca-tools ได้

Lecture 11: OpenStack (cont.?)

Lecture 16.5

Fap fap fap

^ แมวหื่น – -”

^ รู้สินะว่า 16.5 คืออะไร???

วิธีคอมไพล์ mpi กับ cuda

nvcc –compiler-bindir mpicc mpi.c cuda.cu

[a]Chavit Denninnart:

Device คือ CPU ram หรือ การ์ดจอ ?


Chawanat Nakasan:

device always means GPU in this context ;)

Comments are closed.