|
נקודות זכות באוניברסיטה העברית:
3
תואר:
מוסמך
היחידה האקדמית שאחראית על הקורס:
מדעי המחשב
סמסטר:
סמסטר א'
שפת ההוראה:
עברית
קמפוס:
קרית א"י ספרא
מורה אחראי על הקורס (רכז):
ד"ר עודד שוורץ
שעות קבלה של רכז הקורס:
ד 14-15
מורי הקורס:
ד"ר עודד שוורץ
תאור כללי של הקורס:
מחשבי-על מורכבים ממאות אלפי עד מיליוני מעבדים. השימוש בהם חדר בשנים האחרונות לתחומים רבים. התשתית הטכנולוגית של חלקים גדולים משרותי האינטרנט נסמכת על טכנולוגיה זו; מחשבי על משמשים גם לצורך חישוב מדעי וסימולציות באקדמיה ובתעשייה. בעיה מרכזית בחזית המחקר היא שאלגוריתמים קיימים עלולים שלא להתאים למחשבי על, בגלל שני אתגרים משמעותיים:
1) איך להשיג ביצועים גבוהים? בפרט, איך מתמודדים עם צוואר הבקבוק העקרי: עלויות התקשורת בין מעבדים ובתוך הררכית הזכרון? עלויות אלה גבוהות בסדרי גודל יותר מבחינת זמן ואנרגיה מהעלויות של החישובים האריתמטים. לפי מגמות החומרה, חלקן בעלות הכוללת צפוי להוסיף לעלות. מכאן הצורך באלגוריתמים שמורידים למינימום את כמות התקשורת.
2) איך להבטיח עמידות לתקלות? עם עליית גודל המכונות וירידת מתח הפעולה, השכיחות של תקלות רכות (שינוי ביט) ותקלות קשות (נפילת רכיב) צפויה לעלות. צריך לוודא שאם רכיב CPU או GPU מפסיקים לתפקד כראוי, תוצאת החישוב כולה נותרת אמינה. דרושים לכך אלגוריתמים עם יכולת זיהוי ותיקון תקלות.
נסקור דרכי התמודדות עם אתגרים אלה, מכיוונים תאורטיים ומעשים, כפי שהם באים לידי ביטוי בחישובים שונים, כמו כפל מטריצות ואלגברה לינארית, טרנספורם פוריה מהיר, מיונים, אלגוריתמים על גרפים ותכנון דינאמי.
פתוח לסטודנטים לתארים מתקדמים ולסטודנטים לתואר ראשון שנה ג.
דרישות קדם: אלגוריתמים (67504)
מטרות הקורס:
להקנות בסיס תיאורטי, אלגוריתמי, ומעשי של חישוב מקבילי מתקדם
תוצרי למידה :
בסיומו של קורס זה, סטודנטים יהיו מסוגלים:
להשתמש במגוון של שיטות אלגוריתמיות להשגת ביצועים טובים במכונות סדרתיות ובמכונות מקביליות.
להוכיח חסם תחתון של עלויות התקשורת למגוון רחב של חישובים.
לממש אלגוריתמים סדרתיים ומקביליים.
דרישות נוכחות (%):
90
שיטת ההוראה בקורס:
פרונטלית
רשימת נושאים / תכנית הלימודים בקורס:
1. Models of computations.
a. Hardware trends and communication costs.
b. Models: Sequential (2-levels, Hierarchical), Distributed (homogeneous, BSP-like with local memory bound, PRAM), shared.
c. Communication minimizing algorithms: basic examples.
2. Communication minimizing algorithms
a. Sequential classical matrix multiplication: blocked, recursive
b. Parallel classical matrix multiplication: 2D (Cannon, Summa), 3D, 2.5D, BFS-DFS
c. Dense linear algebra: sequential and parallel LU, Cholesky, QR and other decompositions.
d. Sparse numerical linear algebra
e. Weak scaling, strong scaling, perfect strong scaling.
f. Parallel graph algorithms
g. Dynamic programming
h. N-Body problem
3. Communication costs lower bounds: sequential and parallel.
a. Reductions
b. Geometric surface to volume bounds: Loomis–Whitney, Brascamp–Lieb, and Hölder's Inequalities and their applications to matrix multiplication, direct numerical linear algebra, and nested loops.
c. Graph analyses: dominator set, edge expansion, path routing, and their application to Cooley-Tukey FFT, Strassen’s matrix multiplication, and other algorithms.
4. Obliviousness to resources
a. Tuning, auto-tuning and obliviousness
b. Cache oblivious algorithms; Cache eviction policies.
c. Data layouts: row and column major, blocked, recursive.
d. Distributed date layouts, dynamic data layouts
e. Data structure for Cache obliviousness
f. Network and processors obliviousness
5. Networks
a. Common networks: in chips, clusters, and supercomputers
b. Universal networks
c. 2.5D algorithms revisited
d. Topology dependent lower bounds.
6. Resilient computing
a. Hardware trends
b. Fault tolerance
c. Fault tolerance by error correcting codes
7. Non-volatile memories
a. Read-write asymmetry in costs and durability
b. Write spreading algorithms
c. Write lower bounds
d. Write minimizing algorithms
8. Sorting Algorithms
a. Parallelizations of sequential algorithms
b. Funnel-sort
9. Bilinear algorithms
a. Practical fast matrix multiplication, exact and approximated: Strassen-Winograd, Bini, Pan, Hopkroft-Kerr, Smirnov
b. Impractical fast matrix multiplication
c. Yuster-Zwick fast-sparse matrix multiplication
10. Fast Fourier Transform
a. Cooley Tukey
b. Lower bounds
c. Sequential and Parallel implementations
11. Hands-on. A subset of
a. Distributed memory machines: MPI
b. Shared memory machines: OpenMP and Threads
c. GPU: CUDA, CULA, OpenCL
d. Debugging and optimization tools.
e. The roofline model
f. LAPACK and ScaLAPACK
g. FFTW
12. Function on matrices, Newton method, inverse, root, sign.
חומר חובה לקריאה:
יפורט במהלך הקורס.
חומר לקריאה נוספת:
Parallel Scientific Computation: A Structured Approach using BSP and MPI
by Rob H. Bisseling
Introduction to Algorithms
by Thomas H. Cormen et al.
Applied Numerical Linear Algebra
by James W. Demmel
Functions of Matrices: Theory and Computation
by Nicholas J. Higham
מרכיבי הציון הסופי :
מידע נוסף / הערות:
|
