Архитектура VLIW: Перенос сложности на компилятор

Введение

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

Очень длинное командное слово (VLIW) относится к архитектурам наборов команд, разработанным для использования параллелизма на уровне команд (ILP). Процессор VLIW позволяет программам явно указывать инструкции для параллельного выполнения, в то время как обычные центральные процессоры (CPU) в основном позволяют программам указывать инструкции для последовательного выполнения. VLIW призван обеспечить более высокую производительность без сложности, свойственной некоторым другим конструкциям. Традиционные способы повышения производительности процессоров включают разделение инструкций на подэтапы, чтобы инструкции могли выполняться частично одновременно (это называется конвейеризацией), отправку отдельных инструкций для независимого выполнения в разных частях процессора (суперскалярные архитектуры) и даже выполнение инструкций в порядке, отличном от порядка в программе (выполнение вне порядка). Все эти методы усложняют аппаратную часть (увеличивают размер схем, повышают стоимость и энергопотребление), поскольку процессору необходимо самостоятельно принимать все решения для их работы. В отличие от этого, метод VLIW предполагает, что программы предоставляют все решения относительно того, какие инструкции выполнять одновременно и как разрешать конфликты. На практике это означает, что компилятор (программное обеспечение, используемое для создания конечных программ) становится более сложным, но аппаратная часть – проще, чем во многих других подходах к параллелизму.

История

Концепция архитектуры VLIW и термин VLIW были изобретены Джошем Фишером в его исследовательской группе в Йельском университете в начале 1980-х годов. Его оригинальная разработка трассированного планирования как метода компиляции для VLIW была выполнена, когда он был аспирантом в Нью-Йоркском университете. До появления VLIW понятие предварительного планирования исполнительных устройств и параллелизма на уровне инструкций в программном обеспечении было хорошо известно в практике разработки горизонтального микрокода. До Фишера теоретические аспекты того, что впоследствии было названо VLIW, были разработаны советским ученым-компьютерщиком Михаилом Карцевым на основе его работ 1960-х годов над военными компьютерами М9 и М10. Его идеи были позже развиты и опубликованы в виде части учебника за два года до основополагающей работы Фишера, но из-за «железного занавеса» и того, что работа Карцева была преимущественно военной, она оставалась в значительной степени неизвестной на Западе. Инновации Фишера заключались в разработке компилятора, способного генерировать горизонтальный микрокод из программ, написанных на обычном языке программирования. Он понял, что для достижения высокой производительности и поддержки машины с широкой выдачей необходимо находить параллелизм, выходящий за рамки обычно встречающегося в пределах базового блока. Он также разработал методы планирования областей для выявления параллелизма, выходящего за пределы базовых блоков. Планирование трассировки – один из таких методов, который включает в себя планирование наиболее вероятного пути выполнения базовых блоков, вставку компенсирующего кода для обработки спекулятивных переходов, планирование второго наиболее вероятного трасса и так далее, пока расписание не будет завершено. Вторым нововведением Фишера было представление о том, что архитектура целевого процессора должна быть спроектирована таким образом, чтобы быть разумной целью для компилятора; что компилятор и архитектура VLIW-процессора должны разрабатываться совместно. Это было частично вдохновлено трудностями, с которыми Фишер столкнулся в Йельском университете при компиляции для архитектур, таких как FPS164 от Floating Point Systems, которая имела сложную архитектуру вычислительных машин с множеством инструкций (CISC), разделяющую начало выполнения инструкции и инструкции, сохраняющие результат, что требовало очень сложных алгоритмов планирования. Фишер разработал набор принципов, характеризующих правильную конструкцию VLIW, таких как самоочищающиеся конвейеры, широкие многопортовые регистровые файлы и архитектуры памяти. Эти принципы облегчали компиляторам генерацию быстрого кода. Первый VLIW-компилятор был описан в диссертации доктора философии Джона Эллиса под руководством Фишера. Компилятор был назван "Bulldog" – в честь талисмана Йельского университета. Фишер покинул Йель в 1984 году, чтобы основать стартап-компанию Multiflow вместе с соучредителями Джоном О’Доннеллом и Джоном Руттенбергом. Multiflow выпустила серию мини-суперкомпьютеров TRACE на архитектуре VLIW, начав поставки своих первых машин в 1987 году. VLIW-процессор Multiflow мог выполнять 28 операций параллельно за одну инструкцию. Система TRACE была реализована с использованием смеси интеграции среднего (MSI), большого (LSI) и сверхбольшого (VLSI) масштаба, упакованной в шкафы – технология, которая устарела, поскольку стало более экономически выгодно интегрировать все компоненты процессора (за исключением памяти) на одном чипе. Multiflow оказалась слишком ранней, чтобы воспользоваться следующей волной, когда архитектуры чипов начали допускать многопоточную обработку. Крупные полупроводниковые компании признали ценность технологии Multiflow в этом контексте, поэтому компилятор и архитектура были впоследствии лицензированы большинству этих фирм.

The concept of VLIW architecture, and the term VLIW, were invented by Josh Fisher in his research group at Yale University in the early 1980s. His original development of trace scheduling as a compiling method for VLIW was developed when he was a graduate student at New York University. Before VLIW, the notion of prescheduling execution units and instruction level parallelism in software was well established in the practice of developing horizontal microcode. Before Fisher the theoretical aspects of what would be later called VLIW were developed by the Soviet computer scientist Mikhail Kartsev based on his Sixties work on military oriented M 9 and M 10 computers. His ideas were later developed and published as a part of a textbook two years before Fisher's seminal paper, but because of the Iron Curtain and because Kartsev's work was mostly military related it remained largely unknown in the West. Fisher's innovations involved developing a compiler that could target horizontal microcode from programs written in an ordinary programming language. He realized that to get good performance and target a wide issue machine, it would be necessary to find parallelism beyond that generally within a basic block. He also developed region scheduling methods to identify parallelism beyond basic blocks. Trace scheduling is such a method, and involves scheduling the most likely path of basic blocks first, inserting compensating code to deal with speculative motions, scheduling the second most likely trace, and so on, until the schedule is complete. Fisher's second innovation was the notion that the target CPU architecture should be designed to be a reasonable target for a compiler; that the compiler and the architecture for a VLIW processor must be codesigned. This was inspired partly by the difficulty Fisher observed at Yale of compiling for architectures like Floating Point Systems' FPS164, which had a complex instruction set computing (CISC) architecture that separated instruction initiation from the instructions that saved the result, needing very complex scheduling algorithms. Fisher developed a set of principles characterizing a proper VLIW design, such as self draining pipelines, wide multi port register files, and memory architectures. These principles made it easier for compilers to emit fast code. The first VLIW compiler was described in a Ph. D. thesis by John Ellis, supervised by Fisher. The compiler was named Bulldog, after Yale's mascot. Fisher left Yale in 1984 to found a startup company, Multiflow, along with cofounders John O'Donnell and John Ruttenberg. Multiflow produced the TRACE series of VLIW minisupercomputers, shipping their first machines in 1987. Multiflow's VLIW could issue 28 operations in parallel per instruction. The TRACE system was implemented in a mix of medium scale integration (MSI), large scale integration (LSI), and very large scale integration (VLSI), packaged in cabinets, a technology obsoleted as it grew more cost effective to integrate all of the components of a processor (excluding memory) on one chip. Multiflow was too early to catch the following wave, when chip architectures began to allow multiple issue CPUs. The major semiconductor companies recognized the value of Multiflow technology in this context, so the compiler and architecture were subsequently licensed to most of these firms.

Мотивация

Процессор, который выполняет каждую инструкцию последовательно (то есть, не имеет конвейерной скалярной архитектуры), может неэффективно использовать ресурсы, что приводит к потенциально низкой производительности. Производительность можно повысить, одновременно выполняя различные этапы последовательных инструкций (это называется конвейеризацией), или даже выполняя несколько инструкций полностью одновременно, как в суперскалярных архитектурах. Дальнейшее улучшение достигается выполнением инструкций в порядке, отличном от порядка их следования в программе – это называется внеочередным исполнением. Некоторые процессоры добавили несколько арифметико-логических устройств (АЛУ) для параллельной работы. Суперскалярные процессоры используют аппаратные средства для определения того, какие операции могут выполняться параллельно во время выполнения, в то время как процессоры VLIW используют программное обеспечение (компилятор) для предварительного определения, какие операции могут выполняться параллельно. Поскольку сложность планирования инструкций переносится в компилятор, сложность аппаратной части может быть существенно снижена. Схожая проблема возникает, когда результат инструкции, допускающей параллелизацию, используется в качестве входных данных для условного перехода. Большинство современных процессоров предсказывают, какая ветвь будет выбрана, еще до завершения вычисления, чтобы загрузить инструкции для этой ветви или (в некоторых архитектурах) даже начать их спекулятивное выполнение. Если процессор ошибается в предсказании, все эти инструкции и их контекст должны быть отменены, а правильные инструкции загружены, что требует времени. Это привело к усложнению логики выдачи инструкций, которая пытается предсказывать правильно, и простота оригинальных RISC-архитектур была утрачена. VLIW лишена этой логики, а следовательно, и связанного с ней энергопотребления, возможных дефектов проектирования и других негативных аспектов. В VLIW компилятор использует эвристики или профильную информацию для предсказания направления условного перехода. Это позволяет ему перемещать и предварительно планировать операции спекулятивно до выполнения перехода, отдавая предпочтение наиболее вероятному пути. Если переход происходит неожиданным образом, компилятор уже генерирует компенсирующий код для отбрасывания спекулятивных результатов, чтобы сохранить семантику программы. Векторные процессорные ядра (предназначенные для работы с большими одномерными массивами данных, называемыми векторами) могут быть объединены с архитектурой VLIW, как, например, в микропроцессоре Fujitsu FR V, что дополнительно увеличивает пропускную способность и скорость.

A processor that executes every instruction one after the other (i. e., a non pipelined scalar architecture) may use processor resources inefficiently, yielding potential poor performance. The performance can be improved by executing different substeps of sequential instructions simultaneously (termed pipelining), or even executing multiple instructions entirely simultaneously as in superscalar architectures. Further improvement can be achieved by executing instructions in an order different from that in which they occur in a program, termed out of order execution. some CPUs have added several arithmetic logic units (ALUs) to run in parallel. Superscalar CPUs use hardware to decide which operations can run in parallel at runtime, while VLIW CPUs use software (the compiler) to decide which operations can run in parallel in advance. Because the complexity of instruction scheduling is moved into the compiler, complexity of hardware can be reduced substantially. A similar problem occurs when the result of a parallelizable instruction is used as input for a branch. Most modern CPUs guess which branch will be taken even before the calculation is complete, so that they can load the instructions for the branch, or (in some architectures) even start to compute them speculatively. If the CPU guesses wrong, all of these instructions and their context need to be flushed and the correct ones loaded, which takes time. This has led to increasingly complex instruction dispatch logic that attempts to guess correctly, and the simplicity of the original reduced instruction set computing (RISC) designs has been eroded. VLIW lacks this logic, and thus lacks its energy use, possible design defects, and other negative aspects. In a VLIW, the compiler uses heuristics or profile information to guess the direction of a branch. This allows it to move and preschedule operations speculatively before the branch is taken, favoring the most likely path it expects through the branch. If the branch takes an unexpected way, the compiler has already generated compensating code to discard speculative results to preserve program semantics. Vector processor cores (designed for large one dimensional arrays of data called vectors) can be combined with the VLIW architecture such as in the Fujitsu FR V microprocessor, further increasing throughput and speed.

Совместимость с другими технологиями

Когда кремниевая технология позволила создавать более широкие реализации (с большим количеством исполнительных устройств), скомпилированные программы для предыдущего поколения не работали бы на более широких реализациях, поскольку кодировка двоичных инструкций зависела от количества исполнительных устройств машины. Transmeta решила эту проблему, включив в свою реализацию архитектуры x86 Crusoe программный слой компилятора, преобразующего двоичный код в двоичный (называемый морфированием кода). Этот механизм рекламировался как способ перекомпиляции, оптимизации и трансляции x86-опкодов во время выполнения во внутренний машинный код процессора. Таким образом, чип Transmeta внутренне является VLIW-процессором, эффективно отсоединенным от набора инструкций x86 CISC, который он исполняет. Архитектура Itanium от Intel (и другие) решила проблему обратной совместимости с помощью более общего механизма. В каждой из множественных инструкций опкода выделяется битовое поле для указания зависимости от предыдущей VLIW-инструкции в потоке инструкций программы. Эти биты устанавливаются на этапе компиляции, что освобождает аппаратное обеспечение от вычисления этой информации о зависимостях. Наличие этой информации о зависимостях, закодированной в потоке инструкций, позволяет более широким реализациям выдавать несколько независимых VLIW-инструкций параллельно за такт, в то время как более узкие реализации будут выдавать меньшее количество VLIW-инструкций за такт. Другим недостатком VLIW-архитектур считается разрастание кода, возникающее, когда одно или несколько исполнительных устройств не имеют полезной работы и, следовательно, должны выполнять инструкции No Operation (NOP). Это происходит, когда в коде есть зависимости, и конвейеры инструкций должны быть очищены, прежде чем последующие операции смогут быть выполнены. Поскольку количество транзисторов на чипе возросло, значимость предполагаемых недостатков VLIW уменьшилась. VLIW-архитектуры становятся все более популярными, особенно на рынке встраиваемых систем, где можно настроить процессор для конкретного приложения в системе на кристалле.

When silicon technology allowed for wider implementations (with more execution units) to be built, the compiled programs for the earlier generation would not run on the wider implementations, as the encoding of binary instructions depended on the number of execution units of the machine. Transmeta addressed this issue by including a binary to binary software compiler layer (termed code morphing) in their Crusoe implementation of the x86 architecture. This mechanism was advertised to basically recompile, optimize, and translate x86 opcodes at runtime into the CPU's internal machine code. Thus, the Transmeta chip is internally a VLIW processor, effectively decoupled from the x86 CISC instruction set that it executes. Intel's Itanium architecture (among others) solved the backward compatibility problem with a more general mechanism. Within each of the multiple opcode instructions, a bit field is allocated to denote dependency on the prior VLIW instruction within the program instruction stream. These bits are set at compile time, thus relieving the hardware from calculating this dependency information. Having this dependency information encoded in the instruction stream allows wider implementations to issue multiple non dependent VLIW instructions in parallel per cycle, while narrower implementations would issue a smaller number of VLIW instructions per cycle. Another perceived deficiency of VLIW designs is the code bloat that occurs when one or more execution unit(s) have no useful work to do and thus must execute No Operation NOP instructions. This occurs when there are dependencies in the code and the instruction pipelines must be allowed to drain before later operations can proceed. Since the number of transistors on a chip has grown, the perceived disadvantages of the VLIW have diminished in importance. VLIW architectures are growing in popularity, especially in the embedded system market, where it is possible to customize a processor for an application in a system on a chip.