Image Processing

Рань­ше быст­ро­дей­ствие ком­пью­те­ров опре­де­ля­лось так­то­вой ча­сто­той. Она по­вы­ша­лась — и про­грам­мы ра­бо­та­ли быст­рее, не тре­буя для это­го мо­дифи­ка­ции. Но ко­гда даль­ней­шее уве­ли­че­ние так­то­вой ча­сто­ты ста­ло не­воз­мож­ным, вы­чис­ли­тель­ные си­сте­мы на­ча­ли рас­ти «вширь», и ис­поль­зо­ва­ние всех их ре­сур­сов по­тре­бо­ва­ло до­пол­ни­тель­ных зна­ний и уси­лий со сто­ро­ны про­грам­ми­стов.

Кро­ме то­го, все­гда су­ще­ству­ют «боль­шие» за­да­чи, ко­то­рые не по си­лам од­но­му ком­пью­те­ру. Та­кие за­да­чи при­хо­дит­ся ре­шать на па­ра­л­лель­ных вы­чис­ли­тель­ных си­сте­мах, а на­пи­са­ние па­ра­л­лель­ных про­грамм не­воз­мож­но без зна­ния ос­нов па­ра­л­лель­но­го про­грам­ми­ро­ва­ния.

На этой стра­ни­це я бу­ду пуб­ли­ко­вать лек­ции по па­ра­л­лель­но­му про­грам­ми­ро­ва­нию, ко­то­рые я ве­ду в Мос­ков­ском Фи­зи­ко-Тех­ни­че­ском Ин­сти­ту­те (МФТИ) в рам­ках кур­са «Со­вре­мен­ные тех­но­ло­гии па­ра­л­лель­но­го про­грам­ми­ро­ва­ния».

Ес­ли ги­перс­сыл­ка на на­зва­нии лек­ции от­сут­ству­ет, зна­чит, эта лек­ция ещё не на­пи­са­на:

Пер­вый се­местр

• Вве­де­ние
  • Лек­ция № 1: Раз­ви­тие па­ра­л­лель­ных тех­но­ло­гий в пер­со­наль­ных ком­пью­те­рах
  • Лек­ция № 2: Клас­сифи­ка­ция вы­чис­ли­тель­ных си­стем
  • Лек­ция № 3: Свой­ства па­ра­л­лель­ных ал­го­рит­мов
  • Лек­ция № 4: При­ве­де­ние мат­ри­цы к тре­уголь­но­му ви­ду
  • Лек­ция № 5: Пи­ра­ми­даль­ная сор­ти­ров­ка
  • Лек­ция № 6: Сор­ти­ров­ка слия­ни­ем
• Кэш про­цес­со­ра
  • Лек­ция № 7: Кэш про­цес­со­ра
  • Лек­ция № 8: Мно­го­уров­не­вая ар­хи­тек­ту­ра кэш-па­мя­ти в со­вре­мен­ных ком­пью­те­рах
  • Лек­ция № 9: Оп­ти­ми­за­ция про­грамм с учё­том на­ли­чия кэш-па­мя­ти
• Ар­хи­тек­ту­ра мно­го­про­цес­сор­ных/мно­го­ядер­ных си­стем
  • Лек­ция № 10: Ме­ха­низ­мы син­хро­ни­за­ции кэ­шей в мно­го­про­цес­сор­ных и мно­го­ядер­ных си­сте­мах
  • Лек­ция № 11: Ре­аль­ный и за­щи­щён­ный ре­жи­мы про­цес­со­ра
  • Лек­ция № 12: Вир­ту­аль­ная па­мять
  • Лек­ция № 13: Про­цесс и по­ток. Дис­пет­чер про­цес­сов
• Мно­го­по­точ­ность с ис­поль­зо­ва­ни­ем Windows API
  • Лек­ция № 14: Со­зда­ние про­цес­сов и по­то­ков в опе­ра­ци­он­ной си­сте­ме Windows
  • Лек­ция № 15: Функ­ции син­хро­ни­за­ции по­то­ков и про­цес­сов в опе­ра­ци­он­ной си­сте­ме Windows
  • Лек­ция № 16: Па­ра­л­лель­ная реа­ли­за­ция сор­ти­ров­ки слия­ни­ем при по­мо­щи Windows Threads
• Мно­го­по­точ­ность с ис­поль­зо­ва­ни­ем PThreads
  • Лек­ция № 17: Вве­де­ние в PThreads
  • Лек­ция № 18: Со­зда­ние по­то­ков и управ­ле­ние ими
  • Лек­ция № 19: Mutex Variables в PThreads
  • Лек­ция № 20: Объ­ект син­хро­ни­за­ции Condition Variable в PThreads
  • Лек­ция № 21: Ре­ше­ние за­да­чи «обе­даю­щие фи­ло­со­фы» при по­мо­щи PThreads

Вто­рой се­местр

• OpenMP 2.5 (спе­цифи­ка­ция: http://www.openmp.org/mp-documents/spec25.pdf)
  • Лек­ция № 22: Вве­де­ние в OpenMP 2.5
    По­ня­тие об OpenMP. «Ин­кре­мен­таль­ное рас­па­рал­ле­ли­ва­ние». Пул по­то­ков. Мо­дель па­ра­л­лель­но­го вы­пол­не­ния fork-join (стр. 9–10, кон­спект)
  • Лек­ция № 23: Мо­дель па­мя­ти OpenMP
    Мо­дель па­мя­ти. Управ­ляю­щие пе­ре­мен­ные. Ло­каль­ные и об­щие дан­ные. Ди­рек­ти­ва flush (стр. 10–13, 24–25, 58–62)
  • Лек­ция № 24: Ди­рек­ти­ва parallel и па­ра­л­лель­ный до­ступ к дан­ным
    Ди­рек­ти­ва parallel. Ат­ри­бу­ты до­сту­па к дан­ным default, shared, private, firstprivate, lastprivate, reduction (стр. 18–19, 26–28, 63–65, 70–83)
  • Лек­ция № 25: Ди­рек­ти­ва раз­де­ле­ния ра­бо­ты for
    (стр. 32–38, 47)
  • Лек­ция № 26: Ди­рек­ти­вы раз­де­ле­ния ра­бо­ты sections, single, master
    (стр. 32, 39–43, 48–49, 51–52)
  • Лек­ция № 27: Ди­рек­ти­вы син­хро­ни­за­ции critical, barrier, atomic, ordered
    (стр. 52–57)
  • Лек­ция № 28: При­ме­ры реа­ли­за­ции ал­го­рит­мов с ис­поль­зо­ва­ни­ем OpenMP
    Ме­тод Гаус­са ре­ше­ния СЛАУ, сор­ти­ров­ка слия­ни­ем (кон­спект, сор­ти­ров­ка на са­мо­сто­я­тель­ное изу­че­ние)
  • Лек­ция № 29: Биб­лио­те­ка вре­ме­ни вы­пол­не­ния
    Функ­ции omp_set_num_threads, omp_get_num_threads, omp_get_max_threads, omp_get_thread_num, omp_get_num_procs, omp_set_nested, omp_get_wtime (стр. 89–96, 100, 109–110)
  • Лек­ция № 30: Про­грам­ма, со­от­вет­ствую­щая спе­цифи­ка­ции OpenMP. Ча­стые ошиб­ки в OpenMP-про­грам­мах
    Вход и вы­ход в/из па­ра­л­лель­ных сек­ций, од­но­вре­мен­ное вы­пол­не­ние ди­рек­тив все­ми по­то­ка­ми, ча­стые ошиб­ки (стр. 87, кон­спект)
• MPI 1.3 (спе­цифи­ка­ция: http://www.mpi-forum.org/docs/mpi-1.3/mpi-report-1.3-2008-05-30.pdf)
  • Лек­ция № 31: Вы­чис­ли­тель­ные си­сте­мы с рас­пре­де­лён­ной па­мя­тью
    (кон­спект)
  • Лек­ция № 32: Вве­де­ние в MPI 1.3
    По­ня­тие об MPI. «Не­про­зрач­ные объ­ек­ты» MPI (стр. 8–9, 12, кон­спект)
  • Лек­ция № 33: Се­ман­ти­ка об­ме­на со­об­ще­ни­я­ми в MPI
    Кон­тек­сты (ком­му­ни­ка­то­ры), те­ги, по­ря­док со­об­ще­ний (стр. 19–20, 31–34, 45–46)
  • Лек­ция № 34: Бло­ки­рую­щие опе­ра­ции «точ­ка-точ­ка»
    По­ня­тие о бло­ки­рую­щих и не­бло­ки­рую­щих опе­ра­ци­ях. Функ­ции MPI_Send, MPI_Recv, MPI_Get_count, MPI_Bsend, MPI_Ssend, MPI_Rsend (16–18, 20–23, 27–30)
  • Лек­ция № 35: Не­бло­ки­рую­щие опе­ра­ции «точ­ка-точ­ка»
    По­ня­тие о бло­ки­рую­щих и не­бло­ки­рую­щих опе­ра­ци­ях. Функ­ции MPI_Isend, MPI_Ibsend, MPI_Issend, MPI_Irsend, MPI_Irecv (16–17, 37–41)
  • Лек­ция № 36: Ожи­да­ние за­вер­ше­ния не­бло­ки­рую­щих опе­ра­ций
    MPI_Request и его осво­бож­де­ние с по­мо­щью MPI_Request_free. Функ­ции MPI_Wait, MPI_Test, MPI_Waitany, MPI_Testany, MPI_Waitall, MPI_Testall (41–50)
  • Лек­ция № 37: Ти­пы дан­ных. Поль­зо­ватель­ские ти­пы дан­ных
    По­ня­тие о ти­пах дан­ных MPI. Функ­ции MPI_Type_contiguous, MPI_Type_vector, MPI_Type_struct, MPI_Address, MPI_Type_extent, MPI_Type_commit, MPI_Type_free. Кон­стан­ты MPI_LB, MPI_UB (18, 23–27, 62–66, 69–75)
  • Лек­ция № 38: Груп­по­вые опе­ра­ции об­ме­на
    MPI_Barrier, MPI_Bcast, MPI_Gather, MPI_Scatter, MPI_Allgather, MPI_Alltoall (стр. 93–98, 106–107, 111, 113–114)
  • Лек­ция № 39: Опе­ра­ции ре­дук­ции
    Функ­ции MPI_Reduce и MPI_Reduce_scatter. Опе­ра­ции MPI_MAXLOC и MPI_MINLOC (115–120, 127–128)
  • Лек­ция № 40: Груп­пы про­цес­сов. Со­зда­ние ком­му­ни­ка­то­ров
    Функ­ции MPI_Group_size, MPI_Group_rank, MPI_Comm_group, MPI_Group_incl, MPI_Group_excl, MPI_Group_free, MPI_Comm_size, MPI_Comm_rank, MPI_Comm_dup, MPI_Comm_create, MPI_Comm_free (стр. 135–150)
• CUDA 2.2
  • Лек­ция № 41: Гра­фи­че­ский кон­вейер. Ар­хи­тек­ту­ра гра­фи­че­ско­го про­цес­со­ра NVidia
  • Лек­ция № 42: Вве­де­ние в тех­но­ло­гию CUDA