דלג לתוכן הראשי

מודלי תכנות

מודלי תכנות הם מפרטים בסיסיים המגדירים כיצד תוכנה מובנית ומורצת. הם מספקים מסגרת למפתחים לבטא אלגוריתמים ולארגן קוד, ולעיתים מפשטים פרטים ברמה נמוכה של החומרה הבסיסית או סביבת הריצה. מודלים שונים מתאימים לסוגים שונים של בעיות וארכיטקטורות חומרה, ומציעים רמות שונות של הפשטה ושליטה.

בשיעור זה נסקור מודלי תכנות קוונטיים וקלאסיים ונראה כיצד ניתן לשלב ביניהם כדי להפעיל אלגוריתמים בסביבות הטרוגניות. איסקנדר סיטדיקוב נותן לנו סקירה כללית בסרטון הבא.

מודל תכנות עבור QPUs​

נתחיל במודל התכנות למחשבים קוונטיים. מודל התכנות הבסיסי המוכר לכמעט כל מפתח קוונטי הוא ה-Circuit הקוונטי. לא נכנס לפרטי מודל ה-Circuit הקוונטי כאן, מאחר שיש לנו כבר הרצאה מצוינת של ג'ון ווטרוס שמסבירה זאת בפירוט. נציין רק שה-Circuit בנוי מקבוצת קווים (הנקראים wires) המייצגים Qubits, Gates המייצגים פעולות על מצבים קוונטיים, וקבוצת מדידות.

A quantum circuit diagram showing qubits as horizontal lines and quantum gates as boxes or connections between qubits.

מושג חשוב נוסף במודל התכנות לחישוב קוונטי הוא מה שאנחנו קוראים פרימיטיבים חישוביים. פרימיטיבים אלה מייצגים חלק מהמשימות הנפוצות ביותר שמשתמשים מבקשים להשיג עם מחשב קוונטי. קיימים מספר פרימיטיבים זמינים כרגע, כולל Executor. בקורס זה נתמקד בעיקר בפרימיטיבים Sampler ו-Estimator. Sampler מעניק לך את היכולת לדגום מצב שהוכן על ידי ה-Circuit הקוונטי שלך. הוא אומר לך אילו מצבי בסיס חישוביים מרכיבים את המצב הקוונטי שהוכן ב-Circuit הקוונטי שלך. Estimator מאפשר לך להעריך את ערך הציפייה של אובזרבבל עבור מערכת במצב שהוכן על ידי ה-Circuit הקוונטי שלך. הקשר נפוץ הוא הערכת האנרגיה של מערכת במצב ספציפי.

A model histogram of results from sampler. Some states are very likely to be measured, others are very unlikely.

הדבר האחרון שנדון בו בחלק זה הוא טרנספילציה. טרנספילציה היא תהליך של שכתוב Circuit נתון כדי להתאים לאילוצים הפיזיים ולארכיטקטורת ערכת ההוראות (ISA) של מכשיר קוונטי ספציפי. בדומה למהדרים קלאסיים, זה אומר תרגום פעולות יוניטריות מופשטות לערכת Gates המקורית שההתקן היעד יכול לבצע. הוא גם מייעל את הוראות ה-Circuit לביצוע יעיל על מחשבים קוונטיים רועשים, כאשר שגרה זו משנה בהדרגה את מבנה ה-Circuit על ידי החלת מספר שלבי אופטימיזציה.

A diagram of transpilation showing how an abstract circuit is mapped into an instruction set architecture circuit. That is, the circuit is rewritten using the native gates and connectivity of the target hardware.

בדוק את ההבנה שלך​

כמה Qubits יש ב-Circuit למטה? A circuit diagram with four horizontal lines and many gates.

תשובה:

ארבעה.

בדוק את ההבנה שלך​

נניח שאתה מדמה את האלקטרונים במולקולה. אתה רוצה לקרב (א) את אנרגיית המצב הבסיסי של המולקולה, ו-(ב) אילו מצבי בסיס חישוביים הם הדומיננטיים ביותר במצב הבסיסי של המולקולה. בכל מקרה, האם תשתמש בפרימיטיב Estimator או Sampler?

תשובה:

(א) Estimator (ב) Sampler

מודלי תכנות קלאסיים​

קיימים מודלי תכנות רבים למחשבים קלאסיים, אך בחלק זה נתמקד בשניים מהפופולריים ביותר: תכנות מקבילי ותהליכי עבודה מבוססי משימות. באמצעות שני מודלים אלה לצד מודלי תכנות קוונטיים, ניתן לבטא כמעט כל תהליך עבודה היברידי קוונטי-קלאסי בכל רמת מורכבות.

תכנות מקבילי​

תכנות מקבילי הוא מודל המחלק תוכנית לתת-בעיות שניתן לבצע בו-זמנית. ישנם שני פרדיגמות עיקריות של תכנות מקבילי:

  • מקביליות זיכרון משותף (Open Multiprocessing, או OpenMP): משמש לניצול מספר ליבות בתוך צומת חישוב יחיד. חוטי ביצוע חולקים מרחב זיכרון אחד.

  • מקביליות זיכרון מבוזר (Message Passing Interface, או MPI): משמש להתרחבות על פני מספר צמתי חישוב נפרדים. לכל תהליך מרחב זיכרון מבודד משלו.

כאן נתמקד במודל הזיכרון המבוזר מאחר שהוא חיוני למחשוב-על רב-צומתי ולתיאום עבודות קוונטי-קלאסיות הטרוגניות בקנה מידה גדול.

ישנם מספר מושגים שאנחנו צריכים להבין כדי לעבוד במודלי תכנות מקבילי עם זיכרון מבוזר:

  • Process - מופע עצמאי של התוכנית עם מרחב הזיכרון שלו.
  • Rank - מזהה מספר שלם ייחודי המוקצה לכל תהליך, משמש ספציפית לזיהוי השולח והמקבל במהלך תקשורת (לאו דווקא "דירוג" במובן של עדיפות).
  • Synchronization - מנגנון לתיאום בין Ranks ותהליכים שונים.
  • Single program, multiple data (SPMD) - מודל חישוב מופשט שבו מופע קוד מקור יחיד רץ בו-זמנית על מספר תהליכים, כאשר כל אחד פועל על תת-קבוצה שונה של הנתונים הכוללים.
  • Message passing - פרדיגמת התקשורת המשמשת בארכיטקטורות זיכרון מבוזר המאפשרת לתהליכים עצמאיים להחליף נתונים ותוצאות ביניים. היא מסתמכת על פעולות 'send' ו-'receive' מפורשות לתיאום ביצוע בין צמתי חישוב שונים.

קיים תקן בשם MPI המממש את פרדיגמת העברת ההודעות הזו לארכיטקטורות מקביליות. MPI משמש כגילום הפונקציונלי של כל המושגים המפורטים לעיל, ומספק את קריאות הספרייה הספציפיות הדרושות לניהול תהליכים, הקצאת Ranks, הקלת Synchronization, ואפשור Message passing תחת מודל SPMD. כשנאסף את כל המושגים הללו, ניתן לומר שביצוע תוכנית מקבילית מתרחשת באופן הבא:

  • תוכנית מהודרת יחידה (אותו קובץ בינארי) מועתקת ומורצת על ידי משגר עבודות כדי ליצור מספר תהליכים מקבילים על פני מספר צמתים.
  • זרימת הבקרה הראשית של התוכנית מוכתבת על ידי ה-Rank של התהליך. זהו עיקרון SPMD בפעולה: התוכנית משתמשת בלוגיקה מותנית (לדוגמה, if (rank == 0)) כדי להבטיח שרק חלקים מסוימים ומקובלים של הקוד מורצים על ידי תהליכי העובד, בעוד תהליך ראשי (לרוב Rank 0) מטפל באתחול ובאגרגציה הסופית.
  • תקשורת בין תהליכים מתרחשת דרך Message passing (באמצעות MPI), הנקראת בכל פעם שתהליך צריך להחליף נתונים או תוצאות ביניים עם Rank אחר.

מבחינה חזותית, זה ייראה בערך כך:

A diagram of a task being divided between nodes.

בוא ננסה ליישם כמה מהמושגים שזה עתה למדנו בקוד.

ראשית, ננסה להריץ תוכנית מקבילית פשוטה של "שלום עולם" באמצעות OpenMPI, שהיא מימוש של פרוטוקול MPI, תקן להעברת הודעות בתכנות מקבילי. כאן נשתמש בחבילת Python‏ mpi4py, שהיא מחייב Python לתקן Message Passing Interface‏ (MPI).

$ vim mpi-hello-world.py
from mpi4py import MPI
import sys

comm = MPI.COMM_WORLD
rank = comm.Get_rank()
size = comm.Get_size()

sys.stdout.write(f"[Rank {rank}] Hello from process {rank} of {size}!\n")

if rank == 0:
    data = {'answer': 42, 'pi': 3.14}
    sys.stdout.write(f"[Rank {rank}] Sending: {data}\n")
    comm.send(data, dest=1, tag=42)
elif rank == 1:
    data = comm.recv(source=0, tag=42)
    sys.stdout.write(f"[Rank {rank}] Received: {data}\n")

~
~

נשתמש בשני צמתים להרצת תוכנית זו, אותם נציין בסקריפט ההגשה שלנו.

$ vim mpi-hello-world.sh

#!/bin/bash
#
#SBATCH --job-name=mpi-hello-world
#SBATCH --output=mpi-hello-world.out
#SBATCH --nodes=2
#SBATCH --ntasks-per-node=1
#SBATCH --cpus-per-task=1
#SBATCH --partition=normal

/usr/lib64/openmpi/bin/mpirun python /data/ch3/parallel/mpi-hello-world.py

לאחר מכן נריץ את סקריפט ה-shell.

$ sbatch mpi-hello-world.sh

אנחנו יכולים לבדוק את יומני התוצאות של העבודה.

$ cat mpi-hello-world.out | grep Rank

[Rank 1] Hello from process 1 of 2!
[Rank 0] Hello from process 0 of 2!
[Rank 0] Sending: {'answer': 42, 'pi': 3.14}
[Rank 1] Received: {'answer': 42, 'pi': 3.14}

כאן השתמשנו בשני צמתים והתהליך בכל צומת מזוהה כעת על ידי Rank - Rank 0 ו-Rank 1 - המשמשים לקביעת זרימת הבקרה של התוכנית.

תהליכי עבודה מבוססי משימות​

עכשיו בוא נדבר על מודל תכנות תהליך עבודה מבוסס משימות. תהליך עבודה מבוסס משימות מפשט חישוב לגרף אציקלי מכוון (DAG). בגרף זה, כל צומת מייצג משימה או עבודה מסוימת, והקצוות (החצים המחברים את הצמתים) מייצגים את התלויות (נתונים וסדר) ביניהם. מתזמן הוא הרכיב שממפה משימות למשאבים ומתזמר את הביצוע.

דוגמה קונקרטית למודל תהליך עבודה מבוסס משימות המיושם על חישוב קוונטי היא מסגרת Qiskit patterns. Qiskit pattern הוא מסגרת כללית שנועדה לפרק בעיות ספציפיות לתחום לרצף שלבים, במיוחד עבור משימות קוונטיות. זה מאפשר קומפוזביליות חלקה של יכולות חדשות שפותחו על ידי חוקרי IBM Quantum® (ואחרים) ומאפשר עתיד שבו משימות חישוב קוונטי מבוצעות על ידי תשתית חישוב הטרוגנית (CPU/GPU/QPU) רבת עוצמה. ארבעת השלבים של Qiskit pattern הם מיפוי, אופטימיזציה, ביצוע ועיבוד לאחר, כאשר כל המשימות מבוצעות זו אחר זו בצינור. אך עם תהליכי עבודה מבוססי משימות אנחנו לא כבולים לסדר ביצוע ליניארי ויכולים לבצע משימות במקביל. כל משימה בתהליך עבודה יכולה להיות עבודה מקבילית שלמה בפני עצמה. לכן, ניתן לשלב ולהתאים מודלים אלה לתיאור אלגוריתמים מורכבים באופן שרירותי, ומנהל עומס עבודה כמו Slurm יטפל בהם.

A diagram of computing tasks organized into a workflow in which some processes are executed in parallel and others in sequence.

התמונה למעלה ממחישה את Qiskit pattern בפעולה. לתהליך העבודה יש מבנה גרף עם ארבעה שלבים. מבנה דמוי-ענפים זה מתוזמר ומבוצע על ידי המתזמן. הבעיה ממופה לצורה ניתנת-לביצוע-קוונטי (Circuit קוונטי) בשלב הראשוני. בשלב הבא, ה-Circuit הקוונטי הזה מאוחסן עבור חומרה קוונטית ספציפית. התמונה מראה זאת כתהליך מקבילי, אשר מדגים כיצד ניתן להחיל מספר אסטרטגיות אופטימיזציה בו-זמנית. ה-Circuit הקוונטי המאוחסן מורץ לאחר מכן על חומרה הקוונטית בפועל. זהו השלב השלישי של התמונה שבו המתזמן עובד עם יחידת עיבוד קוונטי סגולה אחת. לבסוף, התוצאות עוברות עיבוד לאחר על ידי משאבים קלאסיים.

למה שניהם?​

אז למה אנחנו צריכים גם תכנות מקבילי וגם תהליכי עבודה מבוססי משימות? למרות כל הדיבורים על מקביליות קוונטית, כדאי להבהיר שלא הכל מקבילי בחישוב קוונטי.

השיעור הקודם על תהליך העבודה SQD הזכיר כמה תהליכים שלא ניתן להקביל. לדוגמה, אנחנו צריכים את תוצאות מדידות קוונטיות רבות כדי להקרין את המטריצה שלנו לתת-מרחב בממד ניתן לטיפול. בתורם, אנחנו צריכים את המטריצה המאולכסנת ווקטורי המצב הקשורים כדי לבדוק את העקביות העצמית של המדידות הקוונטיות (באמצעות, לדוגמה, שימור מטען). אחרי כל זה, אנחנו צריכים להחליט אם אנרגיית המצב הבסיסי התכנסה מספיק למטרותינו. שלבים אלה הם בהכרח רצופים ודורשים בדיקת תנאי התכנסות ועקביות עצמית לפני המשך.

A schematic of the workflow specific to sample-based quantum diagonalization. The steps include a variational quantum circuit, using measurements to project the Hamiltonian into a subspace, then using a classical optimizer to update variational parameters in the circuit and repeating.

תהליך עבודה זה יידון בפירוט רב יותר ויומש בחלק הבא. הדבר היחיד שאתה צריך לקחת מחלק זה הוא שתהליכי עבודה מבוססי משימות הכרחיים.

תרגול תכנות​

היופי של מודלי תכנות הוא שניתן לשלב ולהתאים אותם כולם יחד. כשאתה מכיר מודלי תכנות קוונטיים וקלאסיים, ניתן לתאר חישוב הטרוגני של מורכבות שרירותית ולהריצו על חומרה. בוא נתרגל זאת עם דוגמה קטנה של תהליך עבודה משולב, אשר מממש את Qiskit pattern (מפה, אחסן, בצע ועבד לאחר) בתוך Slurm שלמדנו בפרק האחרון. כל אחת מארבע המשימות תהיה עבודת Slurm נפרדת, כל אחת עם משאבים משלה. משימת האופטימיזציה תשתמש ב-MPI כדי לאחסן Circuits במקביל (רק לצורך הדוגמה, כמו התמונה לעיל). משימת הביצוע תשתמש במשאבים קוונטיים ובמודלי תכנות קוונטיים (Circuit ו-Sampler). המשימה האחרונה - עיבוד לאחר - תשתמש שוב ב-MPI במקביל עם משאבים קלאסיים.

מיפוי​

תוכנית mapping.py מיועדת לבנות Circuit מסוג PauliTwoDesign, המשמש לעיתים קרובות בספרות למידת מכונה קוונטית ובספרות בנצ'מרקינג קוונטי, עם אובזרבבל פשוט המודד את ה-Qubit ה-(n−1)th(n-1)^\text{th} בכיוון ZZ של מערכת nn-Qubit עם פרמטרים ראשוניים אקראיים. כל אחד מאלה (ה-Circuit הקוונטי שהומר לקובץ qasm, האובזרבבל, והפרמטרים) יישמר בקובץ נפרד תחת ספריית הנתונים וישמש כקלט בשלב האופטימיזציה.

סקריפט ה-shell של שלב זה (mapping.sh) הוא

#!/bin/bash
#
#SBATCH --job-name=mapping
#SBATCH --output=mapping.out
#SBATCH --nodes=1
#SBATCH --ntasks-per-node=1
#SBATCH --cpus-per-task=1
#SBATCH --partition=normal

srun python /data/ch3/workflows/mapping.py

אשר מגדיר את שם העבודה, פורמט הפלט, ומספר הצמתים/משימות/CPUs.

אופטימיזציה​

תוכנית optimization.py מתחילה על ידי הבאת קבצים משלב המיפוי. כאן תשתמש ב-QRMI כדי להביא משאבים קוונטיים לתוכנית זו.

qrmi = QRMI()
resources = qrmi.resources()
quantum_resource = resources[0]
...

לאחר מכן מבצעת אופטימיזציה קלה על ידי הגדרת optimization_level=1 לטרנספילציה של ה-Circuit הקוונטי והחלת פריסת ה-Circuit על האובזרבבל, ולאחר מכן שומרת אותם לתיקיית הנתונים.

סקריפט ה-shell של שלב זה (optimization.sh) הוא

#!/bin/bash
#SBATCH --job-name=optimization
#SBATCH --output=output/optimization.out
#SBATCH --ntasks=4
#SBATCH --partition=classical

srun python3 /tmp/optimization.py

כאן --ntasks=4 מבקש ארבע משימות קלאסיות מ-Slurm לתהליך מקבילי.

ביצוע​

זהו שלב הקוונטי המרכזי שבו ה-Circuit הקוונטי המאוחסן מהשלב הקודם מורץ על ה-QPU על ידי Estimator. לשם כך, ראשית נביא שלושה קבצים - ה-Circuit הקוונטי שעבר טרנספילציה, האובזרבבל, והפרמטרים הראשוניים - ולאחר מכן נעביר אותם ל-Estimator. הוא מניב את הערך המוערך של האובזרבבל ומדפיס אותו.

סקריפט execution.sh ממנף תוסף Slurm לשימוש במשאב קוונטי.

#!/bin/bash
#
#SBATCH --job-name=execution
#SBATCH --output=execution.out
#SBATCH --nodes=1
#SBATCH --ntasks-per-node=1
#SBATCH --cpus-per-task=1
#SBATCH --partition=quantum
#SBATCH --gres=qpu:1

srun python /data/ch3/workflows/execution.py

עיבוד לאחר​

שלב העיבוד לאחר כולל לעיתים קרובות אלכסון קלאסי ובדיקות עקביות עצמית. הוא עשוי להיות גם איטרטיבי. שימושי ביותר לשקול את שלב העיבוד לאחר בשיעור הבא, שבו ההקשר הפיזי ומטרת השלבים האיטרטיביים ברורים.

שילוב הכל יחד​

ניתן לשרשר את כל המשימות הללו לתהליך עבודה על ידי שימוש בארגומנט התלות עבור פקודת sbatch:

$ MAPPING_JOB=$(sbatch --parsable mapping.sh)
$ OPTIMIZE_JOB=$(sbatch --parsable --dependency=afterok:$MAPPING_JOB optimization.sh)
$ EXECUTE_JOB=$(sbatch --parsable --dependency=afterok:$OPTIMIZE_JOB execute.sh)

ואנחנו יכולים לבדוק את תור הביצוע של Slurm שלנו.

$ squeue
#             JOBID PARTITION     NAME     USER ST       TIME  NODES NODELIST(REASON)
#                 3 classical  mapping    admin PD       0:00      1 (None)
#                 4 classical optimiza    admin PD       0:00      1 (Dependency)
#                 5   quantum  execute    admin PD       0:00      1 (Dependency)

זו הייתה דוגמת צעצוע להדגמת תערובת מודלי התכנות. בפרק הבא נבחן אלגוריתמים מהעולם האמיתי ונדגים מודלי תכנות וניהול משאבים על תהליכי עבודה שימושיים.

סיכום​

בשיעור זה הדגמנו כיצד לשלב מספר מודלי תכנות קלאסיים וקוונטיים כדי לבנות, לנהל ולבצע תהליך עבודה מלא בארבעה שלבים. התחלנו עם המושגים הבסיסיים של Circuits קוונטיים ופרימיטיבים, לאחר מכן חקרנו מודלים קלאסיים כמו תכנות מקבילי ותהליכי עבודה מבוססי משימות. על ידי שילוב כל המושגים, בנינו Qiskit pattern — מפה, אחסן, בצע ועבד לאחר — מתוזמר על ידי מנהל עומס העבודה Slurm עם Circuit קוונטי פשוט ואובזרבבל.

בשיעור הבא, נשתמש במסגרת זו להרצת אלגוריתמים קוונטיים מבוססי דגימה, ונראה כיצד תהליך עבודה זה ניתן ליישום לפתרון בעיות משמעותיות.

כל הקוד והסקריפטים המשמשים בפרק זה זמינים לך במאגר Github הזה.