Параллельные вычисления в многоядерных мультитредовых структурах В.В. Корнеев

Основные препятствия на пути роста тактовой частоты и параллелизма обработки традиционных микропроцессоров ограничение скорости распространения сигналов на кристалле энергопотребление тепловыделение

Области распространения сигнала внутри кристалла за один такт длительностью 8 задержек вентилей с четырьмя нагрузками ( 8FO4)

При технологических нормах 90нм на тактовой частоте 1ГГц 64-разрядный блок операций с плавающей точкой занимает площадь менее, чем 1кв. мм и расходует около 50 pJ энергии на одну операцию передача данных на расстояние, равное одной из сторон кристалла 14ммх14 мм, требует около 1 nJ

Itanium II 421 mm GHZ 1% - обработка 99% - управление пересылкой и хранением данных

Переход к многоядерным кристаллам

Однокристальная система

коммутатор 5х5 ВХ2 ВЫХ2 ВХ3 ВЫХ3 ВХ4 ВЫХ4 ВХ1 ВЫХ1 вычислитель ВХ0 ВЫХ0

Кристалл Tile64

Ядро и структура кэш-памяти Tile 64

Потоковая реализация операции накопления на двухядерном конвейере

Intel 48 core chip

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

GP GPU Fermi

Fermi: 512 (16x32) op или 32-bit flop за такт L2 cache (768KB in size for a 512-core chip)

Fermi provides six 64-bit DRAM channels that support SDDR3 and GDDR5 DRAMs. Up to 6GB of GDDR5 DRAM can be connected to the chip Fermi provides ECC (error correcting code) protection for DRAM; The chips register files, shared memories, L1 and L2 caches are also ECC protected. The level of protection is known as SECDED: single (bit) error correction, double error detection.

Fermi debuts the Parallel Thread eXecution (PTX) 2.0 instruction-set architecture (ISA). All addresses in the GPU are allocated from a continuous 40-bit (one terabyte) address space. Global, shared, and local addresses are defined as ranges within this address space and can be accessed by common load/store instructions. The load/store instructions support 64-bit addresses to allow for future growth. All instructions support predication. Each instruction can be executed or skipped based on condition codes. Predication allows each threadeach coreto perform different operations as needed while execution continues at full speed.

Multiple threads are grouped into thread blocks containing up to 1,536 (32х48) threads. All of the threads in a thread block will run on a single SM, so within the thread block, threads can cooperate and share memory. Thread blocks can coordinate the use of global shared memory among themselves but may execute in any order, concurrently or sequentially.

Thread blocks are divided into warps of 32 threads. The warp is the fundamental unit of dispatch within a single SM. In Fermi, two warps from different thread blocks (even different kernels) can be issued and executed concurrently, increasing hardware utilization and energy efficiency.

The L2 cache subsystem also implements another feature not found on CPUs: a set of memory read-modify-write operations that are atomicthat is, uninterruptibleand thus ideal for managing access to data that must be shared across thread blocks or even kernels. Normally this functionality is provided through a two-step process; a CPU uses an atomic test- and-set instruction to manage a semaphore, and the semaphore manages access to a predefined location or region in memory.

Пути преодоления разрыва в быстродействии элементов памяти и логики

Темп роста быстродействия процессоров и памяти

Использование временной и пространственной локализации кодов программ и обрабатываемых данных виртуальная адресация кэш-память

Организация потока запросов к памяти расслоение памяти с заданной схемой распределения адресов по N блокам памяти (блок i: A modN=i, скремблирование) процессоры с суперскалярной и VLIW-архитектурами

Мультитредовость как средство повышения параллелизма и потока запросов к памяти процессы, треды POSIX pthreads, «лёгкие» треды qthread

FE бит значение FE бита full\empty устанавливает, что слово памяти имеет содержимое или нет команды writeef, readfe, readff и writeff могут выполняться только при определенном в них в первом компоненте суффикса значении бита FE и оставляют после выполнения значение этого бита, заданное компоненте суффикса команды writeff требует, чтобы перед её выполнением значение FE бита слова памяти, в которое будет запись, было full и оставляет после выполнения это же значение

Межтредовая синхронизация и коммуникации традиционные специальные переменные (замки, семафоры, сигналы) неделимые последовательности команд системные запросы ОС Full/Empty биты введение в каждое слово памяти Full/Empty битов синхронизация при каждом обращении к памяти: writeef, readfe, readff и writeff

язык XMTC PRAM (Parallel Random Access Model) eXplicit Multi-Threading (XMT) язык программирования: С + 3 оператора: Spawn, Join и PS (Prex-Sum) PS(e, x) – атомарно возвращает текущее значение х, сохраняя новое х+e $-номер текущего треда

структура мультитредовой программы возможность синхронного и асинхронного выполнения тредов

пример программы psBaseReg x =0; spawn(0,n-1){ int e; e = 1; if(A[$]) != 0){ ps(e,x); B[x] = A[$]; }

Qthread Library Basic Threading –qthread_initqthread_init –qthread_finalizeqthread_finalize - qthread_fork,qthread_fork Futures –future_initfuture_init –future_forkfuture_fork –future_join_allfuture_join_all –future_exitfuture_exit FEB qthread_feb_status qthread_readFE qthread_readFF qthread_writeEF, qthread_writeEF_constqthread_writeEF qthread_writeEF_const qthread_writeF, qthread_writeF_constqthread_writeF qthread_writeF_const –Mutex qthread_lock, qthread_unlockqthread_lock qthread_unlock

Сортировка миллиарда чисел на 48- процессорной Itanium 1.5 ГГц SGI Altix SMP

Умножение матрицы на вектор

Умножение матрицы на вектор с оптимизацией

Мультиядерные мультитредовые потоковые вычисления

Структура программы

Отображение программы на ресурсы

Взаимодействие между процессами в одной и соседних элементарных машинах process 1: S S+sem(S),1(δ) //занесение в конец очереди S объекта δ// process 2: when S>0 do S S-0,1(ε) //выборка из начала очереди S объекта ε// (ip, jq)ВЫХp ВХq ЭМi ЭМj process 1: ВЫХp ВЫХp+sem(ВЫХp),1(δ) process 2: when ВХq>0 do ВХq ВХq-0,1(ε)

Типы структур подсистем

Подсистема типа «дерево» и её восходящее и нисходящее покрывающие деревья

Подсистема типа «дерево»

Итерация решения САУ, i=1, …, n

Korneev.-.Arkhitektura.vychi slitel'nykh.sistem.s.programmiruemoi. strukturoi.zip

Заключение Преодоление разрыва в быстродействии элементов памяти и логики может быть преодолено путём построения ВС на базе мультиядерных мультитредовых кристаллов и использованием в них потоковых мультиредовых программ и программ на базе модели клеточных автоматов