Ran Gildai — Параллельная обработка. Топология Флинна

Используя параллельность, очевидно, можно достигнуть увеличения скорости. Множественная обработка реализует параллелизм. Сетевые процессоры используют различные формы множественной обработки и параллельности. Для того, чтобы рассмотреть вопрос параллелизма семантически, будем использовать терминологию и таксономию Флинна. Данная таксономия основана на двух осях архитектуры: количество потоков управления (потоков инструкций) и количество потоков данных. Термин поток – означает последовательность, либо инструкций, либо данных, которые процессор использует для обработки. Рассмотрим четыре основных типа архитектуры:

SISD архитектура, в которой один поток управления контролирует один поток данных – это классическая архитектура Фон-Неймана, в которой инструкции следуют из памяти в CPU и затем выполняются. Некоторые из этих инструкций могут быть загружены или сохранены из/в память.

Рисунок 1 — SISD архитектура

SIMD архитектура, в которой один поток управления контролирует множество потоков данных. Эта архитектура включает в себя вектор и массив процессоров. Идея заключается в том, что один юнит управления контролирует множество обрабатывающих элементов (например, арифметических функций), в то же время, управляя множественными операциями над данными из/в память.

Рисунок 2 — SIMD архитектура

MISD архитектура, в которой множество потоков управления контролируют один поток данных. Обычно данная архитектура считается экспериментальной. Она включает в себя систолические массивы, конвейерные векторные машины и тому прочее.

Рисунок 3 — MISD архитектура

MIMD архитектура, в которой множественные потоки управления контролируют множество потоков данных. Большинство мультипроцессорных и мультикомпьютерных систем используют данную архитектурную категорию.

Рисунок 4 — MIMD архитектура

В свою очередь категорию MIMD можно разделить на 2 основных класса:

Мультипроцессоры с разделенной памятью – архитектуры тесно связанные, разделяющие общую память.
Мультипроцессоры с распределенной памятью – архитектуры, слабо связанные использующие распределенную память между модулями обработки.

Разделенная память может быть реализована различными способами, несмотря на это, принято использовать такие реализации как Однородный Доступ к Памяти (UMA - Uniform Memory Access), Неоднородный доступ к памяти (NUMA), или (COMA - Cache Only Memory Architecture). В UMA модели, физическая память разделена равномерно между всеми процессорами (хотя процессоры могут обрабатывать память локального кеша). Тесно связанная архитектура обычно приписывается UMA реализациям. NUMA – наоборот; это означает, что некоторые процессоры делят их локальную память, и набор всей локальной памяти создает глобальную память. Также это означает, что доступ к памяти неравномерный (локальные процессоры имеют преимущества). Подкласс NUMA – COMA, подразумевает, что набор всех локальных Кешей создает глобальную память.

Мультикомпьютерные системы, обычно представляют слабо связанные MIMD архитектуры и иногда называются Multiple SISD (M-SISD), используют распределенную или частную память, и включают мультипроцессорные системы с массовым параллелизмом, которые состоят из сеток и гиперкубов, кластеров рабочих станций или сетевых рабочих станций.

Мультипроцессорные системы могут быть разделены в соответствии с различными другими критериями, но наиболее значительная подкатегория – это Симметрические Мультипроцессоры (SMP – Symmetrical Multiprocessors). SMP – тесно связанная архитектура похожих процессоров, которые имеют одинаковый приоритет и память. Другая подкатегория – асимметрические процессоры и совместная обработка данных, которая имеет тесно связанную архитектуру специфических, различных процессоров, которые делят между собой память в общем случае.

Другие категории был определены после таксономии Флинна, среди них были единственная программа для множества потоков данных (SPMD - single program over multiple data streams), и множество программ для множества потоков данных (MPMD - multi-program over multiple data streams).

Современные реализации MIMD – гибридны, в зависимости от разделенной и распределенной памяти, в которых несколько распределенных узлов памяти разделенной между мультипроцессорами, как показано на рисунке 5

Рисунок 5 — MIMD гибридная архитектура

Литература

1. 3GPP, General Packet Radio Service (GPRS) Enhancements for Evolved Universal Terrestrial Radio Access Network (E-UTRAN) Access (Release 8), 3GPP TS 23.401 V8.1.0 (2008-03), 2008.

2. 3GPP, Evolved Universal Terrestrial Radio Access (E-UTRA) and Evolved Universal Terrestrial Radio Access (E-UTRAN); Overall description; Stage 2, 3GPP TS 36.300 V8.4.0 (2008-03), 2008.

3. 3GPP, Evolved Universal Terrestrial Access Network (E-UTRAN), Architecture description, 3GPP TS 36.401 V8.1.0 (2008-03), 2008.

4. 3GPP, Evolved Universal Terrestrial Access Network (E-UTRAN), S1 General Aspects and Principles (Release 8), 3GPP TS 36.410 V8.0.0 (2007–12), 2007.

5. Aboul-Magd, O., Constraint-Based LSP Setup Using LDP (CR-LDP) Extensions for Automatic Switched Optical Network (ASON), RFC 3475, IETF, 2003.

6. Aboul-Magd, O., and Rabie, S., A Differentiated Service Two-Rate, Three-Color Marker with Effi cient Handling of In-Profi le Traffi c, RFC 4115, IETF, 2005.

7. Adams, A., Nicholas, J., and Siadak, W., Protocol Independent Multicast–Dense Mode (PIM-DM): Protocol Specifi cation (Revised), RFC 3973, IETF, 2005.

8. Adelson-Velsky, G. M., and Landis, E. M., An Algorithm for the Organization of Information, Dokady Alademiia Nauk SSSR, 146:263–266, 1962 (translated to English by Ricci, M. K.); also in Soviet Mathematics, Doklady, 3:1259–1263, 1962).

9. Afsharian, S., Bertolino, A., De Angelis, G., Iovanna, P., and Mirandola, R., Model Based Approach to Design Applications for Network Processor, Proceedings of RISE 2004, Lecture Notes in Computer Science, Vol. 3475:93–101, Springer Verlag, 2005.

10. Agere, The Case for a Classifi cation Language, White Paper, http://nps.agere.com/support/ non-nda/docs/Classifi cation_New.pdf, 2001.

11. Aggarwal, R., Rosen, E., Morin, T., Rekhter, Y., and Kodeboniya, C., BGP Encodings and Procedures for Multicast in MPLS/BGP IP VPNs, draft-ietf-l3vpn-2547bis-mcast-bgp, IETF, 2007.

12. Ahmad, S., and Mahapatra R. N., TCAM Enabled On-Chip Logic Minimization, Proceedings of the 42nd ACM/IEEE International Design Automation Conference, pp. 678–683, 2005.

13. Ahmadi, H., and Denzel, W. E., A Survey of Modern High-Performance Switching Techniques, IEEE Journal on Selected Areas in Communications, 7(7):1091–1103, 1989.

14. Allan, D., Bragg, N., McGuire A., and Reid, A., Ethernet as Carrier Transport Infrastructure, IEEE Communications Magazine, 44(2):134–140, 2006.

15. Almquist, P., Type of Service in the Internet Protocol Suite, RFC 1349, IETF, 1992.

16. Alt, H., Blum, N., Mehlhorn, K., and Paul, M., Computing a Maximum Cardinality Matching in a Bipartite Graph in Time O(n3/2 + (m/log n)1/2), Information Processing Letters, 37(4):237–240, 1991.

17. Anderson, T. E., Owicki, S. S., Saxe, J. B., and Thacker, C. P., High-Speed Switch Scheduling for Local-Area Networks, ACM Transaction on Computer Systems, 11(4):319–352, 1993.

18. Andersson, A., and Nilsson, S., Improved Behavior of Tries by Adaptive Branching, Information Processing Letters, 46:295–300, 1993.

19. Andersson, L., and Madsen, T., Provider Provisioned Virtual Private Network (VPN) Terminology, RFC 4026, IETF, 2005.