Портирование ядра операционной системы Linux

• Аннотация
• Данный дипломный проект содержит в себе описание процесса портирования ядра операционной системы Linux, приводится аналитический обзор существующих разработок.
• Характеристики дипломного проекта:
• · Объем составляет 70 страниц.
• · Количество графических материалов составляет 9 листов
• · Количество литературных источников составляет 10 позиций.
• Введение

В программировании под портированием понимают адаптацию некоторой программы или её части, с тем чтобы она работала в другой среде, отличающейся от той среды, под которую она была изначально написана. Процесс портирования также называют портингом (от англ. porting), а результат — портом.

Портируемость (переносимость, англ. portability) обычно относится к одной из двух вещей:

1. Портируемость — как возможность единожды откомпилировав код (обычно в некоторый промежуточный код, который затем компилируется во время исполнения, «на лету», англ. Just-In-Time), затем запускать его на множестве платформ без каких-либо изменений.

2. Портируемость — как свойство программного обеспечения, описывающее, насколько легко это ПО может быть портировано. По мере развития операционных систем, языков и техники программирования, становится всё проще портировать программы между различными платформами. Одной из изначальных целей создания языка С и стандартной библиотеки этого языка — была возможность простого портирования программ между несовместимыми аппаратными платформами. Дополнительные преимущества в плане портируемости могут иметь программы, удовлетворяющие специальным стандартам и правилам написания.

Международные стандарты (в частности, продвигаемые международной организацией по стандартизации ISO) значительно упрощают портирование, благодаря тому что они описывают среду исполнения программ таким образом, что различия между платформами становятся минимальными. Часто портирование программ между платформами, реализующими один и тот же стандарт (такой как POSIX.1) сводятся к перекомпиляции программы на новой платформе.

Существует также всё расширяющийся набор инструментов, облегчающих портирование, например, таких как компилятор GCC, предоставляющий неизменный язык программирования на различных платформах.

Некоторые языки программирования высокого уровня (Eiffel, Esterel) достигают портируемости путем трансляции исходного кода в промежуточный язык, имеющий компиляторы для многих процессоров и операционных систем.

1. Специальная часть.

1.1 Постановка задачи.

Необходимость в выполнении портирования операционной системы возникает в силу различий в наборе операций процессора, различий между интерфейсами операционной системы, различий в оборудовании, либо по причине несовместимости или даже полного отсутствия используемого языка программирования в целевом окружении.

На базе ядра Linux может быть создана необходимая конфигурация операционной системы и, поэтому данная операционная система может быть использована в качестве средства для управления процессорами MIPS-архитектуры.

В рамках проекта необходимо произвести портирование ядра Linux в микропроцессорную систему MIPS-архитектуры и провести тестирование полученного порта.

Целью дипломного проекта является разработка порта Linux и проведение тестирования полученного порта операционной системы для конкретного микропроцессора MIPS-архитектуры, аналога MIPS64.

1.2 Обзор предметной области.

Термин «архитектура системы» часто употребляется как в узком, так и в широком смысле этого слова. В узком смысле под архитектурой понимается архитектура набора команд. Архитектура набора команд служит границей между аппаратурой и программным обеспечением и представляет ту часть системы, которая видна программисту или разработчику компиляторов. Следует отметить, что это наиболее частое употребление этого термина. В широком смысле архитектура охватывает понятие организации системы, включающее такие высокоуровневые аспекты разработки компьютера как систему памяти, структуру системной шины, организацию ввода/вывода и т. п.

Двумя основными архитектурами набора команд, используемыми компьютерной промышленностью на современном этапе развития вычислительной техники являются архитектуры CISC и RISC.

RISC (англ. Reduced Instruction Set Computing) — вычисления с сокращённым набором команд.

Это концепция проектирования процессоров, которая во главу ставит следующий принцип: более компактные и простые инструкции выполняются быстрее. Простая архитектура позволяет удешевить процессор, поднять тактовую частоту, а также распараллелить исполнение команд между несколькими блоками исполнения (т.н. суперскалярные архитектуры процессоров). Многие ранние RISC-процессоры даже не имеют команд умножения и деления. Идея создания RISC процессоров пришла после того, как в 1970;х годах ученые из IBM обнаружили, что многие из функциональных особенностей традиционных ЦПУ игнорировались программистами. Отчасти это был побочный эффект сложности компиляторов. В то время компиляторы могли использовать лишь часть из набора команд процессора. Следующее открытие заключалось в том, что, поскольку некоторые сложные операции использовались редко, они как правило были медленнее, чем те же действия, выполняемые набором простых команд. Это происходило из-за того, что создатели процессоров тратили гораздо меньше времени на улучшение сложных команд, чем на улучшение простых.

Первые RISC-процессоры выполняли небольшой (50?100) набор команд, тогда как обычные CISC (Complex Instruction Set computer) выполняли 100—200.

Характерные особенности RISC-процессоров:

· Фиксированная длина машинных инструкций (например, 32 бита) и простой формат команды.

· Специализированные команды для операций с памятью — чтения или записи. Операции вида «прочитать-изменить-записать» отсутствуют. Любые операции «изменить» выполняются только над содержимым регистров (т.н. load-and-store архитектура).

· Большое количество регистров общего назначения (32 и более).

· Отсутствие поддержки операций вида «изменить» над укороченными типами данных — байт, 16-битное слово. Так, например, система команд DEC Alpha содержала только операции над 64-битными словами, и требовала разработки и последующего вызова процедур для выполнения операций над байтами, 16- и 32-битными словами.

· Отсутствие микропрограмм внутри самого процессора. То, что в CISC процессоре исполняется микропрограммами, в RISC процессоре исполняется как обыкновенный (хотя и помещенный в специальное хранилище) машинный код, не отличающийся принципиально от кода ядра ОС и приложений. Так, например, обработка отказов страниц в DEC Alpha и интерпретация таблиц страниц содержалась в так называемом PALCode (Privileged Architecture Library), помещенном в ПЗУ. Заменой PALCode можно было превратить процессор Alpha из 64битного в 32битный, а также изменить порядок байт в слове и формат входов таблиц страниц виртуальной памяти.

Основой архитектуры современных рабочих станций и серверов является архитектура компьютера с сокращенным набором команд. Зачатки RISC-архитектуры уходят своими корнями к компьютерам CDC6600, разработчики которых (Торнтон, Крэй и др.) осознали важность упрощения набора команд для построения быстрых вычислительных машин. Эту традицию упрощения архитектуры С. Крэй с успехом применил при создании широко известной серии суперкомпьютеров компании Cray Research. Однако окончательно понятие RISC в современном его понимании сформировалось на базе трех исследовательских проектов компьютеров: процессора 801 компании IBM, процессора RISC университета Беркли и процессора MIPS Стенфордского университета.

Разработка экспериментального проекта компании IBM началась еще в конце 70-х годов, но его результаты никогда не публиковались и компьютер на его основе в промышленных масштабах не изготавливался. В 1980 году Д. Паттерсон со своими коллегами из Беркли начали свой проект и изготовили две машины, которые получили названия RISC-I и RISC-II. Главными идеями этих машин было отделение медленной памяти от высокоскоростных регистров и использование регистровых окон.

В 1981 году Дж. Хеннесси со своими коллегами опубликовал описание стенфордской машины MIPS, основным аспектом разработки которой была эффективная реализация конвейерной обработки посредством тщательного планирования компилятором его загрузки.

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

Развитие архитектуры RISC в значительной степени определялось прогрессом в области создания оптимизирующих компиляторов. Именно современная техника компиляции позволяет эффективно использовать преимущества большего регистрового файла, конвейерной организации и большей скорости выполнения команд. Современные компиляторы используют также преимущества другой оптимизационной техники для повышения производительности, обычно применяемой в процессорах RISC: реализацию задержанных переходов и суперскалярной обработки, позволяющей в один и тот же момент времени выдавать на выполнение несколько команд.

Первое время RISC-архитектуры с трудом принимались рынком из-за отсутствие программного обеспечения для них. Эта проблема была быстро решена переносом UNIX-подобных операционных систем на RISC архитектуры.

1.3 Анализ аналогичных разработок.

1.3.1 Особенности архитектуры MIPS компании MIPS Technology.

MIPS (англ. Microprocessor without Interlocked Pipeline Stages — «микропроцессор без блокировок в конвейере») — семейство RISC-микропроцессоров, разработаное компанией MIPS Technologies. Архитектура MIPS использовалась в старых компьютерах SGI, а также во встроенных системах и в игровых консолях Nintendo 64, Sony PlayStation, Sony PlayStation 2 и Sony PSP.

Первые процессоры MIPS были 32-битными, позже была разработана 64-битная архитектура.

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

В настоящий момент процессоры архитектуры MIPS широко используются во встраиваемых устройствах с критичной производительностью.

Семейство процессоров с архитектурой MIPS:

· R1000 (не выпускался: лабораторный образец). У него отсутствовало умножение и деление (они выполнялись программно).

· R2000.

· R3000.

· R4000.

· R5000.

· RM7000.

· RM9000.

· R8000.

· R10000 (последний созданный MIPS); его дальнейшие модификации с увеличенным кэшем и частотой:

o R12000.

o R14000.

o R16000.

· существуют различные модификации других фирм.

Архитектура MIPS была одной из первых RISC-архитектур, получившей признание со стороны промышленности. Она была анонсирована в 1986 году. Первоначально это была полностью 32-битовая архитектура, которая включала 32 регистра общего назначения, 16 регистров плавающей точки и специальную пару регистров для хранения результатов выполнения операций целочисленного умножения и деления. Размер команд составлял 32 бит, в ней поддерживался всего один метод адресации, и пользовательское адресное пространство также определялось 32 битами. Выполнение арифметических операций регламентировалось стандартом IEEE 754. В компьютерной промышленности широкую популярность приобрели 32-битовые процессоры R2000 и R3000, которые в течение достаточно длительного времени служили основой для построения рабочих станций и серверов компаний Silicon Graphics, Digital, Siemens Nixdorf и др. Процессоры R3000/R3010 работали на тактовой частоте 33 или 40 МГц и обеспечивали производительность на уровне 20 SPECint92 и 23 SPECfp92.

Затем на смену микропроцессорам семейства R3000 пришли новые 64-битовые микропроцессоры R4000 и R4400. (MIPS Technology была первой компанией выпустившей процессоры с 64-битовой архитектурой). Набор команд этих процессоров (спецификация MIPS II) был расширен командами загрузки и записи 64-разрядных чисел с плавающей точкой, командами вычисления квадратного корня с одинарной и двойной точностью, командами условных прерываний, а также атомарными операциями, необходимыми для поддержки мультипроцессорных конфигураций. В процессорах R4000 и R4400 реализованы 64-битовые шины данных и 64-битовые регистры. В этих процессорах применяется метод удвоения внутренней тактовой частоты.

Процессоры R2000 и R3000 имели стандартные пятиступенчатые конвейеры команд. В процессорах R4000 и R4400 применяются более длинные конвейеры (иногда их называют суперконвейерами). Количество ступеней в процессорах R4000 и R4400 увеличилось до восьми, что объясняется прежде всего увеличением тактовой частоты и необходимостью распределения логики для обеспечения заданной пропускной способности конвейера. Процессор R4000 может работать с тактовой частотой 50/100 МГц и обеспечивает уровень производительности в 58 SPECint92 и 61 SPECfp92. Процессор R4400 может работать на частоте 50/100 МГц, или 75/150 МГц, показывая уровень производительности 94 SPECint92 и 105 SPECfp92.

Внутренняя кэш-память процессора R4000 имеет емкость 16 Кбайт. Она разделена на 8-Кб кэш команд и 8-Кб кэш данных. С точки зрения реализации кэш-памяти процессор R4400 имеет более развитые возможности. Он выпускается в трех модификациях: PC (Primary Cashe) — имеет внутренние кэши команд и данных емкостью по 16 Кбайт. Процессор в такой конфигурации предназначен главным образом для дешевых моделей рабочих станций. SC (Secondary Cashe) содержит логику управления кэш-памятью второго уровня. MC (Multiprocessor Cashe) — использует специальные алгоритмы обеспечения когерентности и согласованного состояния памяти для многопроцессорных конфигураций.

В середине 1994 года компания MIPS анонсировала процессор R8000, который прежде всего был ориентирован на научные прикладные задачи с интенсивным использованием операций с плавающей точкой. Этот процессор построен на двух кристаллах (выпускается в виде многокристальной сборки) и представляет собой первую суперскалярную реализацию архитектуры MIPS. Теоретическая пиковая производительность процессора для тактовой частоты 75 МГц составляет 300 MFLOPs (до четырех команд и шести операций с плавающей точкой в каждом такте). Реализация большой кэш-памяти данных емкостью 16 Мбайт, высокой пропускной способности доступа к данным (до 1.2 Гбайт/с) в сочетании с высокой скоростью выполнения операций позволяет R8000 достигать 75% теоретической производительности даже при решении больших задач типа LINPACK с размерами матриц 1000×1000 элементов. Аппаратные средства поддержки когерентного состояния кэш-памяти вместе со средствами распараллеливания компиляторов обеспечивают возможность построения высокопроизводительных симметричных многопроцессорных систем. Например, процессоры R8000 используются в системе Power Challenge компании Silicon Graphics, которая вполне может сравниться по производительности с известными суперкомпьютерами Cray Y-MP, имеет на порядок меньшую стоимость и предъявляет значительно меньшие требования к подсистемам питания и охлаждения. В однопроцессорном исполнении эта система обеспечивает производительность на уровне 310 SPECfp92 и 265 MFLOPs на пакете LINPACK (1000×1000).

В 1994 году MIPS Technology объявила также о создании своего нового суперскалярного процессора R10000, начало массовых поставок которого ожидалось в конце 1995 года. По заявлениям представителей MIPS Technology R10000 обеспечивает пиковую производительность в 800 MIPS при работе с внутренней тактовой частотой 200 МГц за счет обеспечения выдачи для выполнения четырех команд в каждом такте синхронизации. При этом он обеспечивает обмен данными с кэш-памятью второго уровня со скоростью 3.2 Гбайт/с.

Чтобы обеспечить столь высокий уровень производительности в процессоре R10000 реализованы многие последние достижения в области технологии и архитектуры процессоров (Рис. 1).

Рис. 1. Блок-схема микропроцессора R10000.

1.3.2 Иерархия памяти.

При разработке процессора R10000 большое внимание было уделено эффективной реализации иерархии памяти. В нем обеспечиваются раннее обнаружение промахов кэш-памяти и параллельная перезагрузка строк с выполнением другой полезной работой. Реализованные на кристалле кэши поддерживают одновременную выборку команд, выполнение команд загрузки и записи данных в память, а также операций перезагрузки строк кэш-памяти. Заполнение строк кэш-памяти выполняется по принципу «запрошенное слово первым», что позволяет существенно сократить простои процессора из-за ожидания требуемой информации. Все кэши имеют двухканальную множественно-ассоциативную организацию с алгоритмом замещения LRU.

1.3.3 Кэш память данных первого уровня.

Кэш-память данных первого уровня процессора R10000 имеет емкость 32 Кбайт и организована в виде двух одинаковых банков емкостью по 16 Кбайт, что обеспечивает двухкратное расслоение при выполнении обращений к этой кэш-памяти. Каждый банк представляет собой двухканальную множественно-ассоциативную кэш-память с размером строки (блока) в 32 байта. Кэш данных индексируется с помощью виртуального адреса и хранит теги физических адресов памяти. Такой метод индексации позволяет выбрать подмножество кэш-памяти в том же такте, в котором формируется виртуальный адрес. Однако для того, чтобы поддерживать когерентность с кэш-памятью второго уровня, в кэше первого уровня хранятся теги физических адресов памяти.

Массивы данных и тегов в каждом банке являются независимыми. Эти четыре массива работают под общим управлением очереди формирования адресов памяти и схем внешнего интерфейса кристалла. В очереди адресов могут одновременно находиться до 16 команд загрузки и записи, которые обрабатываются в четырех отдельных конвейерах. Команды из этой очереди динамически выдаются для выполнения в специальный конвейер, который обеспечивает вычисление исполнительного виртуального адреса и преобразование этого адреса в физический. Три других параллельно работающих конвейера могут одновременно выполнять проверку тегов, осуществлять пересылку данных для команд загрузки и завершать выполнение команд записи в память. Хотя команды выполняются в строгом порядке их расположения в памяти, вычисление адресов и пересылка данных для команд загрузки могут происходить неупорядоченно. Схемы внешнего интерфейса кристалла могут выполнять заполнение или обратное копирование строк кэш-памяти, либо операции просмотра тегов. Такая параллельная работа большинства устройств процессора позволяет R10000 эффективно выполнять реальные многопроцессорные приложения.

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

При обнаружении промаха при обращении к кэш-памяти данных ее работа не блокируется, т. е. она может продолжать обслуживание следующих запросов. Это особенно полезно для уменьшения такого важного показателя качества реализованной архитектуры как среднее число тактов на команду (CPI — clock cycles per instruction). На Рис. 2 представлены результаты моделирования работы R10000 на нескольких программах тестового пакета SPEC. Для каждого теста даны два результата: с блокировкой кэш-памяти данных при обнаружении промаха (вверху) и действительное значение CPI R10000 (внизу). Выделенная более темным цветом правая область соответствует времени, потерянному из-за промахов кэш-памяти. Верхний результат отражает полную задержку в случае, если бы все операции по перезагрузке кэш-памяти выполнялись строго последовательно. Таким образом, стрелка представляет потери времени, которые возникают в блокируемом кэше. Эффект применения неблокируемой кэш-памяти сильно зависит характеристик самих программ. Для небольших тестов, рабочие наборы которых полностью помещаются в кэш-памяти первого уровня, этот эффект не велик. Однако для более реальных программ, подобных тесту tomcatv или тяжелому для кэш-памяти тесту compress, выигрыш оказывается существенным.

Рис. 2. Моделирование работы R10000 на нескольких компонентах пакета SPEC.

1.3.4 Кэш память данных второго уровня.

Интерфейс кэш-памяти второго уровня процессора R10000 поддерживает 128-битовую магистраль данных, которая может работать с тактовой частотой до 200 МГц, обеспечивая скорость обмена до 3.2 Гбайт/с (для снижения требований к быстродействию микросхем памяти предусмотрена также возможность деления частоты с коэффициентами 1.5, 2, 2.5 и 3). Все стандартные синхронные сигналы управления статической памятью вырабатываются внутри процессора. Не требуется никаких внешних интерфейсных схем. Минимальный объем кэш-памяти второго уровня составляет 512 Кбайт, максимальный размер — 16 Мбайт. Размер строки этой кэш-памяти программируется и может составлять 64 или 128 байт.

Одним из методов улучшения временных показателей работы кэш-памяти является построение псевдо-множествнно-ассоциативной кэш-памяти. В такой кэш-памяти частота промахов находится на уровне частоты промахов множественно-ассоциативной памяти, а время выборки при попадании соответствует кэш-памяти с прямым отображением. Кэш-память R10000 организована именно таким способом, причем для ее реализации используются стандартные синхронные микросхемы памяти (SRAM). В одном наборе микросхем памяти находятся оба канала кэша. Информация о частоте использования этих каналов хранится в схемах управления кэшем на процессорном кристалле. Поэтому после обнаружения промаха в первичном кэше из наиболее часто используемого канала вторичного кэша считываются две четырехсловные строки. Их теги считываются вместе с первой четырехсловной строкой, а теги альтернативного канала читаются одновременно со второй четырехсловной строкой (это осуществляется простым инвертированием старшего разряда адреса).

При этом возможны три случая. Если происходит попадание по первому каналу, то данные доступны немедленно. Если происходит попадание по альтернативному каналу, происходит повторное чтение вторичного кэша. Если отсутствует попадание по обоим каналам, вторичный кэш должен перезаполняться из основной памяти.

Для обеспечения целостности данных в кэш-памяти большой емкости обычной практикой является использование кодов исправляющих одиночные ошибки (ECC-кодов). В R10000 с каждой четырехсловной строкой хранится 9-битовый ECC-код и бит четности. Дополнительный бит четности позволяет сократить задержку, поскольку проверка на четность может быть выполнена очень быстро, чтобы предотвратить использование некорректных данных. При этом, если обнаруживается корректируемая ошибка, то чтение повторяется через специальный двухтактный конвейер коррекции ошибок.

1.3.5 Кэш память команд.

Объем внутренней двухканальной множественно-ассоциативной кэш-памяти команд составляет 32 Кбайт. В процессе ее загрузки команды частично декодируются. При этом к каждой команде добавляются 4 дополнительных бит, которые указывают исполнительное устройство, в котором она будет выполняться. Таким образом, в кэш-памяти команды хранятся в 36-битовом формате. Размер строки кэш-памяти команд составляет 64 байта.

1.3.6 Обработка команд перехода.

При реализации конвейерной обработки возникают ситуации, которые препятствуют выполнению очередной команды из потока команд в предназначенном для нее такте. Такие ситуации называются конфликтами. Конфликты снижают реальную производительность конвейера, которая могла бы быть достигнута в идеальном случае. Одним из типов конфликтов, с которыми приходится иметь дело разработчикам высокопроизводительных процессоров, являются конфликты по управлению, которые возникают при конвейеризации команд перехода и других команд, изменяющих значение счетчика команд.

Конфликты по управлению могут вызывать даже большие потери производительности суперскалярного процессора, чем конфликты по данным. По статистике среди команд управления, меняющих значение счетчика команд, преобладают команды условного перехода. Таким образом, снижение потерь от условных переходов становится критически важным вопросом. Имеется несколько методов сокращения приостановок конвейера, возникающих из-за задержек выполнения условных переходов. В процессоре R10000 используются два наиболее мощных метода динамической оптимизации выполнения условных переходов: аппаратное прогнозирование направления условных переходов и «выполнение по предположению» (speculation).

Устройство переходов процессора R10000 может декодировать и выполнять только по одной команде перехода в каждом такте. Поскольку за каждой командой перехода следует слот задержки, максимально могут быть одновременно выбраны две команды перехода, но только одна более ранняя команда перехода может декодироваться в данный момент времени. Во время декодирования команд к каждой команде добавляется бит признака перехода. Эти биты используются для пометки команд перехода в конвейере выборки команд.

Направление условного перехода прогнозируется с помощью специальной памяти (branch history table) емкостью 512 строк, которая хранит историю выполнения переходов в прошлом. Обращение к этой таблице осуществляется с помощью адреса команды во время ее выборки. Двухбитовый код прогноза в этой памяти обновляется каждый раз, когда принято окончательное решение о направлении перехода. Моделирование показало, что точность двухбитовой схемы прогнозирования для тестового пакета программ SPEC составляет 87%.

Все команды, выбранные вслед за командой условного перехода, считаются выполняемыми по предположению (условно). Это означает, что в момент их выборки заранее не известно, будет ли завершено их выполнение. Процессор допускает предварительную обработку и прогнозирование направления четырех команд условного перехода, которые могут разрешаться в произвольном порядке. При этом для каждой выполняемой по предположению команды условного перехода в специальный стек переходов записывается информация, необходимая для восстановления состояния процессора в случае, если направление перехода было предсказано неверно. Стек переходов имеет глубину в 4 элемента и позволяет в случае необходимости быстро и эффективно (за один такт) восстановить конвейер.

сборка ядро perl операционный.

1.3.7 Структура очередей команд.

Процессор R10000 содержит три очереди (буфера) команд (очередь целочисленных команд, очередь команд плавающей точки и адресную очередь). Эти три очереди осуществляют динамическую выдачу команд в соответствующие исполнительные устройства. С каждой командой в очереди хранится тег команды, который перемещается вместе с командой по ступеням конвейера. Каждая очередь осуществляет динамическое планирование потока команд и может определить моменты времени, когда становятся доступными операнды, необходимые для выполнения каждой команды. Кроме того, очередь определяет порядок выполнения команд на основе анализа состояния соответствующих исполнительных устройств. Как только ресурс оказывается свободным очередь выдает команду в соответствующее исполнительное устройство.

1.3.8 Очередь целочисленных команд.

Очередь целочисленных команд содержит 16 строк и выдает команды в два арифметико-логических устройства. Целочисленные команды поступают в свободные строки этой очереди, причем в каждом такте в нее могут записываться до 4 команд. Целочисленные команды остаются в очереди до тех пор, пока они не будут выданы в одно из АЛУ.

1.3.9 Очередь команд плавающей точки.

Очередь команд плавающей точки также содержит 16 строк и выдает команды в исполнительные устройства сложения и умножения с плавающей точкой. Команды плавающей точки поступают в свободные строки очереди, причем в каждом такте в нее могут записываться до 4 команд. Команды остаются в очереди до тех пор, пока они не будут выданы в одно из исполнительных устройств. Очередь команд плавающей точки содержит также логику управления команд типа «умножить-сложить». Эта команда сначала направляется в устройство умножения, а затем прямо в устройство сложения.

1.3.10 Адресная очередь.

Очередь адресных команд выдает команды в устройство загрузки/записи и содержит 16 строк. Очередь организована в виде циклического буфера FIFO (first-in first-out). Команды могут выдаваться в произвольном порядке, но должны записываться в очередь и изыматься из нее строго последовательно. В каждом такте в очередь могут поступать до 4 команд. Буфер FIFO поддерживает первоначальную последовательность команд, что упрощает обнаружение зависимостей по адресам. Выполнение выданной команды может не закончиться при обнаружении зависимости по адресам, кэш-промаха или конфликта по ресурсам. В этих случаях адресная очередь должна заново повторять выдачу команды до тех пор, пока ее выполнение не завершится.

1.3.11 Переименование регистров.

Одним из аппаратных методов минимизации конфликтов по данным является метод переименования регистров (register renaming). Он получил свое название от широко применяющегося в компиляторах метода переименования — метода размещения данных, способствующего сокращению числа зависимостей и тем самым увеличению производительности при отображении необходимых исходной программе объектов (например, переменных) на аппаратные ресурсы (например, ячейки памяти и регистры).

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

В процессе выполнения программы генерируется множество временных регистровых результатов. Эти временные значения записываются в регистровые файлы вместе с постоянными значениями. Временное значение становится новым постоянным значением, когда завершается выполнение команды (фиксируется ее результат). В свою очередь, завершение выполнения команды происходит когда все предыдущие команды успешно завершились в заданном программой порядке. Программист (или компилятор) имеет дело только с логическими регистрами. Реализация физических регистров от него скрыта.

Таким образом, аппаратный метод переименования регистров, используемый в процессоре R10000, имеет три основных достоинства. Во-первых, результаты «выполняемых по предположению» команд могут прямо записываться в регистровый файл. Во-вторых, этот метод устраняет все конфликты типа «запись после чтения» и «запись после записи», которые часто возникают при неупорядоченном выполнении команд. И, наконец, метод переименования регистров упрощает контроль зависимостей по данным. Поскольку процессор обеспечивает выдачу для выполнения до четырех команд в каждом такте, в процессе переименования регистров их логические номера сравниваются для определения зависимостей между четырьмя командами, декодированными в одном и том же такте.

Реализованная в микропроцессоре R10000 схема отображения команд состоит из двух таблиц отображения, списка активных команд и двух списков свободных регистров (для целочисленных команд и команд плавающей точки имеются отдельные таблицы отображения и списки свободных регистров). Чтобы поддерживать последовательный порядок завершения выполнения команд, существует только один список активных команд, который содержит как целочисленные команды, так и команды плавающей точки.

Микропроцессор R10000 содержит по 64 физических регистра (целочисленных и плавающей точки). В любой момент времени значение физического регистра содержится в одном из указанных выше списков. На Рис. 3 показана упрощенная блок-схема отображения целочисленных команд.

Команды выбираются из кэша команд и помещаются в таблицу отображения. В любой момент времени каждый из 64 номеров физических регистров находится в одном из трех указанных на рисунке блоков.

Список активных команд длиною 32 элемента может хранить упорядоченную в соответствии с программой последовательность команд, которые могут находиться в обработке в любой данный момент времени. Команды из очереди целочисленных команд могут выполняться неупорядочено и записывать результаты в физические регистры, но порядок их окончательного завершения определяется списком активных команд.

Рис. 3. Упрощенная блок-схема отображения целочисленных команд.

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

Когда в процессе переименования из списка свободных регистров выбирается очередной номер физического регистра, он передается в таблицу отображения, которая обновляется. При этом старый номер регистра, соответствующий определенному в команде логическому регистру результата, помещается из таблицы отображения в список активных команд. Этот номер остается в списке активных команд до тех пор, пока соответствующая команда не «выпустится» (graduate), т. е. завершится в заданном программой порядке. Команда может «выпуститься» только после того, как успешно завершится выполнение всех предыдущих команд.

Микропроцессор R10000 содержит 64 физических и 32 логических целочисленных регистра. Список активных команд может содержать максимально 32 элемента. Список свободных регистров также может максимально содержать 32 значения. Если список активных команд полон, то могут быть 32 «зафиксированных» и 32 временных значения. Отсюда потребность в 64 регистрах.

1.3.12 Исполнительные устройства.

В процессоре R10000 имеются пять полностью независимых исполнительных устройств: два целочисленных АЛУ, два основных устройства плавающей точки с двумя вторичными устройствами плавающей точки, которые работают с длинными операциями деления и вычисления квадратного корня, а также устройство загрузки/записи.

1.3.13 Целочисленный АЛУ.

В микропроцессоре R10000 имеются два целочисленных АЛУ: АЛУ1 и АЛУ2. Время выполнения всех целочисленных операций АЛУ (за исключением операций умножения и деления) и частота повторений составляют один такт.

Оба АЛУ выполняют стандартные операции сложения, вычитания и логические операции. Эти операции завершаются за один такт. АЛУ1 обрабатывает все команды перехода, а также операции сдвига, а АЛУ2 — все операции умножения и деления с использованием итерационных алгоритмов. Целочисленные операции умножения и деления помещают свои результаты в регистры EntryHi и EntryLo.

Во время выполнения операций умножения в АЛУ2 могут выполняться другие однотактные команды, но сам умножитель оказывается занятым. Однако когда умножитель заканчивает свою работу, АЛУ2 оказывается занятым на два такта, чтобы обеспечить запись результата в два регистра. Во время выполнения операций деления, которые имеют очень большую задержку, АЛУ2 занято на все время выполнения операции.

Целочисленные операции умножения вырабатывают произведение с двойной точностью. Для операций с одинарной точностью происходит распространение знака результата до 64 бит прежде, чем он будет помещен в регистры EntryHi и EntryLo. Время выполнения операций с двойной точностью примерно в два раза превосходит время выполнения операций с одинарной точностью.

1.3.14 Устройства плавающей точки.

В микропроцессоре R10000 реализованы два основных устройства плавающей точки. Устройство сложения обрабатывает операции сложения, а устройство умножения — операции умножения. Кроме того, существуют два вторичных устройства плавающей точки, которые обрабатывают длинные операции деления и вычисления квадратного корня.

Время выполнения команд сложения, вычитания и преобразования типов равно двум тактам, а скорость их поступления в устройство составляет 1 команда/такт. Эти команды обрабатываются в устройстве сложения. Команды преобразования целочисленных значений в значения с плавающей точкой с однократной точностью имеют задержку в 4 такта, поскольку они должны пройти через устройство сложения дважды.

В устройстве умножения обрабатываются все операции умножения с плавающей точкой. Время их выполнения составляет два такта, а скорость поступления — 1 команда/такт. Устройства деления и вычисления квадратного корня выполняют операции с использованием итерационных алгоритмов. Эти устройства не конвейеризованы и не могут начать выполнение следующей операции до тех пор, пока не завершилось выполнение текущей команды. Таким образом, скорость повторения этих операций примерно равна задержке их выполнения. Порты умножителя являются общими и для устройств деления и вычисления квадратного корня. В начале и в конце операции теряется по одному такту (для выборки операндов и для записи результата).

Операция с плавающей точкой «умножить-сложить», которая в вычислительных программах возникает достаточно часто, выполняется с использованием двух отдельных операций: операции умножения и операции сложения. Команда «умножить-сложить» (MADD) имеет задержку 4 такта и скорость повторения 1 команда/ такт. Эта составная команда увеличивает производительность за счет устранения выборки и декодирования дополнительной команды.

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

1.3.15 Устройство загрузки/записи и TLB.

Устройство загрузки/записи содержит очередь адресов, устройство вычисления адреса, устройство преобразования виртуальных адресов в физические (TLB), стек адресов, буфер записи и кэш-память данных первого уровня. Устройство загрузки/записи выполняет команды загрузки, записи, предварительной выборки, а также команды работы с кэш-памятью.

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

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

TLB содержит 64 строки и выполняет преобразование виртуального адреса в физический. Виртуальный адрес для преобразования поступает либо из устройства вычисления адреса, либо из счетчика команд.

1.3.16 Интерфейс кэш-памяти второго уровня.

Внешняя кэш-память второго уровня управляется с помощью внутреннего контроллера, который имеет специальный порт для подсоединения кэш-памяти. Специальная магистраль данных шириной в 128 бит осуществляет пересылки данных на внутренней тактовой частоте процессора 200 МГц, обеспечивая максимальную скорость передачи данных кэш-памяти второго уровня 3.2 Гбайт/с. В процессоре имеется также 64-битовая шина данных системного интерфейса.

Кэш-память второго уровня имеет двухканальную множественно-ассоциативную организацию. Максимальный размер этой кэш-памяти — 16 Мбайт. Минимальный размер — 512 Кбайт. Пересылки осуществляются 128-битовыми порциями (4 32-битовых слова). Для пересылки больших блоков данных используются последовательные циклы шины:

· Четырехсловные обращения (128 бит) используются для команд кэш-памяти (CASHE);

· Восьмисловные обращения (256 бит) используются для перезагрузки первичного кэша данных;

· Шестнадцатисловные обращения (512 бит) используются для перезагрузки первичного кэша команд;

· Тридцатидвухсловные обращения (1024 бит) используются для перезагрузки кэш-памяти второго уровня.

1.3.17 Системный интерфейс.

Системный интерфейс процессора R10000 работает в качестве шлюза между самим процессором, связанным с ним кэшем второго уровня и остальной системой. Системный интерфейс работает с тактовой частотой внешней синхронизации (SysClk). Возможно программирование работы системного интерфейса на тактовой частоте 200, 133, 100, 80, 67, 57 и 50 МГц. Все выходы и входы системного интерфейса синхронизируются нарастающим фронтом сигнала SysClk, позволяя ему работать на максимально возможной тактовой частоте.

В большинстве микропроцессорных систем в каждый момент времени может происходить только одна системная транзакция.

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

1.4 Обоснование выбора операционной системы.

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

Строго говоря, Linux — это только ядро ОС, находящее в свободном публичном доступе. Системные библиотеки и утилиты разрабатываются сообществом GNU (http://www.gnu.org), поэтому иногда название ОС пишется как GNU/Linux — с целью подчеркнуть заслуги GNU. Уже в 1993 г. Linux можно было полноценно использовать для решения многих задач!

Говоря о Linux, невозможно не упомянуть о социальном феномене разработки Linux. GPL, лицензия, под которой распространяется ядро Linux, предусматривает свободное внесение изменений и их распространение. Дополнительные возможности такого программного обеспечения привлекают новых пользователей, некоторые из них оказываются достаточно активными, чтобы выявлять ошибки, и компетентными, чтобы их исправлять. Этот простой и понятный способ сотрудничества дает фантастические результаты, особенно в разработке драйверов и исправлении ошибок.

Первоначально портирование Linux на платформы, отличные от i386, не предполагалось, однако через три года после начала разработки ОС появился порт Linux на аппаратную архитектуру DEC Alpha (эту работу спонсировала компания Digital Equipment). На сегодняшний день Linux поддерживает целый ряд 32- и 64-разрядных архитектур и процессоров: Sun SPARC и UltraSPARC, Motorola 68 000, PowerPC, PowerPC64, ARM, Hitachi SuperH, IBM S/390, MIPS, HP PA-RISC, Intel IA-64, DEC VAX, AMD x86−64 и CRIS. Такое разнообразие архитектур не ведет к распылению усилий разработчиков, а, наоборот, заставляет строить ядро системы с высоким уровнем абстракций и модульности, повышать качество его кода. Множество поддерживаемых архитектур подтверждает и масштабируемость Linux — от мобильных телефонов и КПК до мейнфреймов.

Linux / MIPS является портом широко распространенного UNIX клона Linux для архитектуры MIPS. Linux / MIPS может работает с большим количеством технически весьма различных систем, начиная от небольших встроенных систем до больших настольных машин и серверов.

Благодаря общему происхождению и одинаковому API, современные ядра Unix имеют много общих черт. За некоторым исключением это монолитные статические бинарные файлы. Они существуют в виде больших исполняемых образов, которые выполняются один раз и используют одну копию адресного пространства. Для работы Unix обычно требуется система с контроллером управления страничной адресацией памяти (MMU, Memory Management Unit); эта система позволяет обеспечить защиту памяти в системе и предоставить каждому процессу виртуальное адресное пространство. Ядро Linux не базируется на какой-то версии Unix, оно является монолитным, однако поддерживает некоторые свойства микроядерной архитектуры. Отличия Linux от других разновидностей Unix:

Поддержка динамически загружаемых модулей ядра. Хотя ядро Linux является монолитным оно дополнительно поддерживает динамическую загрузку и выгрузку кода по мере необходимости. Эта возможность впервые появилась в версии 0.99 благодаря Питеру Мак-Дональду. Часто в виде модулей поставляются драйверы устройств.

Ядро Linux поддерживает симметричную многопроцессорную обработку (SMP). Большинство коммерческих вариантов Unix поддерживают SMP, но большинство традиционных реализаций этой поддержки не имеет.

Ядро Linux является преемптивным. Ядро в состоянии вытеснить выполняющееся задание, даже если оно работает в режиме ядра. Среди коммерческих реализаций Unix преемптивное ядро имеют только Solaris, IRIX, и сам Unix.

В Linux использован иной подход к реализации потоков: потоки ничем не отличаются от обычных процессов. С точки зрения ядра все процессы одинаковы, просто некоторые из них имеют общие ресурсы.

В ядре Linux отсутствуют некоторые функции Unix, которые считаются плохо реализованными (например, STREAMS).

Ядро Linux создается с использованием компилятора GNU C. Причем разработчики ядра используют расширение C ISO C99, поддерживающее функции с подстановкой тела (объявляются с помощью ключевых слов static inline), ассемблерные вставки (используется директива компилятора asm ()), аннотацию ветвлений (макросы likely () и unlikely () — более вероятное и менее вероятное события; используются для оптимизации кода) и другие возможности.

Ядро Linux полностью открыто. Заметим, что сборки ОС GNU/Linux (дистрибутивы) от разных производителей зачастую основываются на ядре, отличном от оригинального (канонического) ядра, выпускаемого разработчиками.

1.5 Разработка .

Ядро операционной системы имеет некоторые специфические особенности в сравнении с программами, которые выполняются в пространстве пользователя. Вот некоторые из них:

· Ядро не имеет доступа к стандартным библиотекам языка C. Причина этого — скорость выполнения и объем кода. Даже самая необходимая часть библиотеки — очень большая и неэффективная для ядра. Часть функций, однако, реализованы в ядре. Например, обычные функции работы со строками описаны в файле lib/string.c.

· Отсутствие защиты памяти. Если обычная программа предпринимает попытку некорректного обращения к памяти, ядро может аварийно завершить процесс. Если ядро предпримет попытку некорректного обращения к памяти, результаты могут быть менее контролируемыми. К тому же ядро не использует замещение страниц: каждый байт, используемый в ядре — это один байт физической памяти.

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

· Фиксированный стек. Стеком называют область адресного пространства, в которой выделяются локальные переменные. Локальные переменные — это все переменные, объявленные внутри левой открывающей фигурной скобки тела функции (или любой другой левой фигурной скобки) и не имеющие ключевого слова static. Стек в режиме ядра ни большой, ни изменяющийся. Поэтому в коде ядра не рекомендуется использоватьрекурсию. Обычно стек равен двум страницам памяти, что соответствует 8 Кбайт для 32-разрядных систем и 16 Кбайт для 64 -разрядных.

· Переносимость. Платформо-независимый код, написанный на языке C, должен компилироваться без ошибок на максимально возможном количестве систем.

1.5.1 Perl-эмулятор.

Отличительными особенностями MIPS 64 реализации фирмы KEDAH являются:

· Отсутствие операций с плавающей точкой (программная эмуляция FPU математического сопроцессора).

· TLB — 32 входное.

· Раздельный кэш данных и кэш команд — по 32 КБайт.

· Шина адреса — 32-разрядная.

Руководствуясь задачами применения разработанного процессора, в эмуляторе были реализованы только следующие основные регистры:

В силу особенностей реализации процессора фирмой KEDAH, в качестве средства кросс-отладки операционной системы использовался собственный эмулятор kem-2.0.2, написанный на языке Perl.

Использование эмулятора позволяет провести отладку выполнения программ до физической реализации микропроцессорной системы, что является менее трудоемким и сокращает финансовые затраты на предварительную аппаратную реализаци. В эмулятор заложены возможности: