Комп'ютерна архітектура і закон Амдала
За час навчання я не вивчав комп'ютерні технології, тому вся моя діяльність в області проектування базувалася виключно на особистому досвіді і необхідності вирішення поточних завдань. В общем-то, і всі мої досягнення в сфері комп'ютерної архітектури укладаються в рамки короткої автобіографії.
WISC
Мій науковий керівник професор Роберт Сакс знав про виниклі ускладнення і влітку 1950 року відрядив мене на два місяці на Абердинский випробувальний полігон в штаті Меріленд. Моя задача полягала в тому, щоб запрограмувати надзвуковий потік, огинає тривимірне тіло. Треба було використовувати набір інструкцій комп'ютера EDVAC (Electronic Discrete Variable Automatic Computer), який в той час знаходився ще в процесі розробки [1] . Я не мав жодного уявлення ні про програмування, ні про архітектуру комп'ютера, і навіть на двомісячні курси програмування мене не відправляли. Стало відомо, що розробка EDVAC призупинилася через те, що ртутні лінії затримки вели себе нестабільно при підвищенні температури.
Не можу сказати, що я був в захваті від архітектури EDVAC, тому що використання операцій з фіксованою точкою поряд з обмеженою довжиною слова вимагало серйозного масштабування для підтримки прийнятної точності. Повернувшись в Вісконсін, я спроектував трьохадресних структуру з плаваючою точкою, намагаючись зробити її якомога простіше і використовуючи доступні на той момент в комерційних продуктах технології. В якості основного засобу зберігання я вибрав магнітний барабан, а для мінімізації числа електронних компонентів використовувалася рециркуляція регістрів. Введення-виведення передбачалося здійснювати за допомогою паперової стрічки і телетайпа, який пробивав отвори на стрічці, зчитував з неї дані і виводив інформацію на друк.
Незабаром я прийшов до висновку, що якщо мені вдасться знайти спосіб перенесення сегментів з одного слова в інше, то можна буде обмежитися операціями з плаваючою точкою. Як трьохадресних операції використовувалася операція Extract, яка отримувала n біт з першого слова, починаючи з біта j, вставляла ці біти в друге слово перед бітом k і записувала результат по третьому адресою. Таке рішення виключало необхідність написання більш десятка інструкцій з фіксованою точкою.
Кожна арифметична операція виконувалася за одне обертання барабана. Тоді я думав, що винайшов новий спосіб поділу. На першій ітерації значення залишку приймалося рівним чисельнику дробу, потім із залишку вираховувався знаменник і в чергову позицію приватного додавалася одиниця, після чого знаменник зміщувався на один біт вправо, і операція повторювалася заново. Як тільки залишок ставав негативним, знаменник не вираховувати, а підсумовувати з ним, після чого одиниця віднімалася з відповідної позиції приватного. Згодом мені стало відомо, що цей метод запатентував Джон фон Нейман.
При виконанні будь-якої операції один оборот барабана був потрібний для зчитування інструкції, другий - для вибірки операндів, третій - для виконання операції і, нарешті, четвертий - для запису результату. Оскільки ніяких конфліктів в процесі виконання операцій не виникало, в конвеєрі постійно перебували чотири інструкції: перша вибирала команду, друга - операнди, третя виконувала операцію, а четверта зберігала результат. Комп'ютер послідовно виконував одну операцію з плаваючою точкою за один оборот барабана. Тут вперше використовувалися відразу кілька конструкторських рішень: вперше електронний комп'ютер мав арифметику з плаваючою точкою (причому тільки з плаваючою точкою), вперше з'явився конвеєр, вперше операції введення-виведення виконувалися одночасно і незалежно від обчислювальних операцій.
Своїми ідеями в області проектування комп'ютерної архітектури я поділився з одним із товаришів, той передав вподобану йому інформацію на кафедру електротехніки, і восени 1950 роки мене запросили прочитати лекцію про розроблений архітектурний проект. Я провів семінар, а ще через тиждень завідувач кафедри електротехніки звернувся до мого наукового керівника з пропозицією змінити тему моєї дисертації і включити туди проект комп'ютерної архітектури, що дозволяв аспірантам потренуватися в новій для себе області. Мій професор погодився, і наступні півроку я витратив на написання нової дисертації і проектування магнітного барабана. У червні 1951 року дисертація була готова, і через місяць я планував захистити її, але виявилося, що ніхто в університеті не володіє достатніми знаннями для її оцінки. В результаті роботу направили вченим на Абердинском випробувальному полігоні. Дисертація на тему «Логічне проектування середньошвидкісних цифрового комп'ютера» була схвалена, а в лютому наступного року я успішно захистив її. Комп'ютер отримав назву WISC (Wisconsin Integrally Synchronized Computer). Роботи над ним було завершено в 1955 році (зараз він знаходиться в музеї комп'ютерної історії в Маунтін-В'ю).
Робота в IBM
Копія моєї дисертації якимось чином опинилася в руках глави відділення IBM в Мілуокі, а звідти потрапила в дослідницький центр компанії в Покіпсі. З нею ознайомився Натаніель Рочестер, після чого я отримав офіційне запрошення приєднатися до команди IBM. У червні 1952 роки я перейшов в IBM, і першим завданням для мене стало моделювання нейронних мереж на машині IBM 701 на основі характеристик, викладених в монографії Дональда Хебба.
Всього було випущено 18 екземплярів моделі 701, після чого її вирішили зняти з виробництва - наступний комп'ютер, IBM 704, повинен був використовувати вже нову пам'ять на магнітних сердечниках, а не на лампах. Відповідно, і ємність пам'яті була значно більше. Проектування пам'яті доручили мені, тому що всі інші інженери IBM були зайняті тоді в спільному з МТІ проект по розробці і створенню системи SAGE (Semi-Automatic Ground Environment) [2]. Я вирішив подвоїти розмір інструкції, з тим щоб вмістити там довший адреса, додаткові команди арифметики з плаваючою точкою, а також арифметики 701 з фіксованою точкою. В одному з англійських комп'ютерів в той час був присутній лічильник B-box, який дозволяв повторювати цикл, зменшуючись після виконання кожної його ітерації на одиницю, до тих пір, поки не ставав рівним нулю. Однак будь-яка зміна адресації в масиві для кожної ітерації як і раніше потребувало окремих інструкцій. Тоді я подумав, що ефективніше було б пов'язати число етапів з їх розмірами - тоді програма могла б стати коротше і швидше. Відповідне рішення було названо індексацією і зажадало вбудовування в модель 704 трьох індексних регістрів, які визначали розміри етапів для конкретних масивів даних. Два біта в інструкції служили для ідентифікації одного з трьох індексних регістрів або відсутності індексації. Ми помітили, що вміст індексного регістра є вже на ранній стадії, завдяки чому адреса в інструкції можна змінити ще до початку вибірки даних, причому це не вимагало додаткових витрат часу. Згодом з'ясувалося, що в системі SAGE теж були присутні функції індексування, а ось кому належало першість, я не знаю - проект носив конфіденційний характер, його подробиці не розкривалися, тому конкретну дату винаходу визначити не вдалося.
Щоб зрозуміти, за якою ціною ми зможемо продавати модель 704, потрібно оцінити масштаби ринку. Спочатку в штаб-квартирі IBM планували продати шість машин (думаю, вони враховували той факт, що 18 проданих моделей 701 в основному вже задовольнили потреби ринку). Таке рішення привело мене в лють, я доводив, що нова машина має набагато більш розвиненими можливостями в порівнянні з моделлю 701 і, відповідно, межі ринку для неї повинні стати ширше. Через кілька тижнів ми домовилися про випуск 12 машин, потім 18 і, нарешті, 32, після чого я зняв свої заперечення. В результаті було продано 140 примірників 704, завдяки чому ця модель стала неймовірно прибутковою для того часу.
Після завершення робіт мені було запропоновано зайнятися проектуванням такої системи, моделі 709, а потім і суперкомп'ютера Stretch, в якому планувалося використовувати нові транзисторні технології. Всі говорили, що це буде мій проект і в ході розробки потрібно лише врахувати вимоги контракту, який передбачалося укласти з лабораторією ім. Лоуренса в Ліверморі або з Національною лабораторією в Лос-Аламосі. У листопаді 1954 року народження, порадившись з Джоном Бекуса, ми визначили принципові характеристики, якими повинен був володіти Stretch. Я вивчав можливості запропонованої напівпровідникової технології і нового типу схем на основі емітерний-зв'язаної логіки, схожою на двотактні підсилювачі вакуумних ламп. Схеми працювали дуже швидко і споживали багато електроенергії. Я брав участь в проектуванні умножителя, намагаючись зрозуміти, на яку продуктивність можна розраховувати в разі вибору ефективної системи команд. Потім почалася робота над новою концепцією «попередньої вибірки», що дозволяє заздалегідь знаходити потрібну гілку алгоритму і без затримок вибирати альтернативну послідовність інструкцій. За підсумками аналізу проект виглядав досить багатообіцяючим, а за критерієм продуктивності новий комп'ютер обіцяв в кілька разів випереджати машини, що створювалися на основі електронних ламп.
Озброївшись попередніми результатами, я попрямував в Лівермор. Там мене вислухали дуже доброзичливо, але повідомили, що вже підписали договір з конкурентом. Після цього я наніс візит в Лос-Аламос. Перебувала там група виявила до проекту жвавий інтерес, і між нами почалися переговори. До цього часу я вже вдосконалив проект Stretch і визначив, що потрібно поліпшити в моделі 704 в процесі переходу до 709. У проекті 709 з'явився цілий ряд вельми корисних інструкцій. Одна з найбільш цікавих команд виконувала «пошук в таблиці з урахуванням історії», що дозволяв здійснювати перетворення з основної кодування IBM BCD (Binary-Coded Decimal) в кодування ASCII (American Standard Code for Information Interchange) і назад. З'явилася також можливість виконувати операції додавання і віднімання двох двійковій-десяткових чисел (кожен десятковий розряд займав шість біт) в двійковому поданні. Використовувалася при цьому таблиця допомагала перетворювати результат в коректний код BCD.
Основним нововведенням став канал введення-виведення, що дозволяв комп'ютера виконувати читання або запис певної кількості даних на магнітну стрічку або барабан. Обмін даними з оперативною пам'яттю передбачалося здійснювати без участі процесора, як це було в WISC. Обчислення в цей час виконувалися з урахуванням затримок циклів пам'яті, обумовлених конфліктами, які виникали при виконанні запитів до оперативної пам'яті. Плановане нами зміна вимагало особливо дорогих розробок, в зв'язку з чим його необхідно було затверджувати у керівництва. Ми з Елейн Боем розуміли, що отримаємо схвалення лише в разі якоїсь карколомної демонстрації. Вирішено було зупинитися на програмі сортування з використанням магнітної стрічки. Машина IBM 703, продана міністерству фінансів США, вже вміла виконувати функції сортування, проте ціна моделі 709, за нашими оцінками, повинна була в два-три рази перевищувати вартість IBM 703. Запрограмувавши сортування, ми переконалися в тому, що на 709 все виконується набагато швидше і вартість операції сортування тут в результаті виявляється нижче, ніж на 703. Ця демонстрація дозволила обгрунтувати запропоновані рішення, і розробку каналу введення-виведення затвердили.
В кінці 50-х років головний науковий радник IBM Емануель Піоро, підпорядковувався безпосередньо Тому Уотсону, приїхавши в Лос-Анджелес, запросив мене з дружиною на обід. Мені запропонували посаду начальника підрозділу експериментальних машин в IBM Research з умовою перебування на східному узбережжі США від чотирьох до семи місяців в році. Подумавши, ми з дружиною прийняли запрошення, і в листопаді 1960 року я повернувся в штат Нью-Йорк. В першу чергу я мав наглядати за проектами свого підрозділу. Ознайомившись зі станом справ, я відразу скасував два апаратних проекту, які не уявляли цінності для IBM. Один з цих проектів, що передбачав створення нового комп'ютера, постійно змінювався, але так і не досяг того рівня завершеності, при якій його можна було б оцінити. Інший, що виконувався на замовлення уряду, передбачав використання надпровідникових перемикачів для створення логічних компонентів, але знайти спосіб посилення впав рівня сигналів розробникам так і не вдалося. Таким чином, в моєму веденні залишилися програмні проекти і потенційний проект нового суперкомп'ютера, для якого не було достатнього фінансування. Я все ж не залишав надію отримати його, оскільки суперкомп'ютер Stretch так і не досяг бажаної продуктивності і ціни на нього були знижені. Моделі 704, 709 і пішли за ними 7090 і 7094 допомагали IBM зберігати стійкі позиції на ринку наукових обчислень.
На той час в компанії вже був сформований комітет SPREAD (Systems Programming, Research, Engineering And Development). Різні підрозділи IBM підтримували п'ять основних комп'ютерних сімейств, кожне з яких поділялося на покоління, не цілком сумісні один з одним. На жаль, загальна вартість розробки росла дуже швидко, оскільки підключення будь-якого нового пристрою передбачало реалізацію інженерного і програмного проекту, який вимагав окремого фінансування. Перед комітетом SPREAD стояла задача визначення форматів даних, пристроїв введення-виведення, технологій управління, зберігання і логічних схем, які необхідно було стандартизувати, а також планування нового сімейства комп'ютерів, яке прийшло б на зміну існуючим. Це було грандіозне підприємство навіть з політичної точки зору, яке вимагало від васалів повної передачі своїх напрацювань королю. Комп'ютерна революція вже почалася, і ставки були високі - йшлося про збереження у IBM контролю за ринком засобів обробки даних.
Повернувшись на пару місяців, я получил от президента підрозділу Data Systems Division Боба Еванса запрошення взяти участь в засіданні бюджетного комітету, Пожалуйста наочно продемонструвало всі проблеми з фінансуванням розробки. После Засідання Боб живити мене, чи згоден я зайнятий проектування нового сімейства комп'ютерів. Я, зі свого боку, поставивши запитання, чи буде Забезпечувати в Першу Черга вісхідна сумісність и лишь потім спадна, и ВІН відповів, что план Полягає самє в цьом. Тоді я помітив, що така постановка питання мені не подобається, оскільки в кінцевому підсумку з бюджетом виникнуть ті ж проблеми, з якими мені вже доводилося стикатися, - відміну поколінь проявляє себе відразу. А між тим сімейства могли б відрізнятися більш високим рівнем сумісності як у висхідному, так і в низхідному напрямку і при цьому фактично без будь-яких додаткових витрат. Боб подумав і відповів згодою. Так в 1961 році я повернувся в Покіпсі, де працював приблизно по десять годин на день, визначаючи формати даних, набори інструкцій, а в деяких випадках і архітектуру обладнання. Кожен новий член родини повинен був приблизно в три рази перевершувати по продуктивності попереднього. Сімейство System 360 налічувало в цілому сім машин, причому остання випереджала першу по продуктивності приблизно в 600 разів. Сімейство мейнфреймів компанії удосконалювалося протягом десятиліть і стало продуктом, котрі принесли IBM найбільший дохід.
У той час я отримав доступ до стрічкових сховищ і до історичних даних комерційних, наукових, інженерних та університетських обчислювальних центрів, в яких були розгорнуті найрізноманітніші наші машини, починаючи від 704 і закінчуючи 7094. Аналіз цих відомостей дозволив отримати інформацію про відносне використанні різних інструкцій і цікаву статистику. Історія робочого навантаження обчислювальних центрів свідчила про те, що на кожну виконану інструкцію припадав один біт введення-виведення. Я зміг оцінити швидкість виконання обчислювальних операцій при заданому обсязі пам'яті. У багатопроцесорної середовищі продуктивність залежала від швидкості роботи дисків і стрічок, яку я визначив в 1969 році. Тоді ж з'ясувалося, що System 360 повинна була міняти довжину адреси для досягнення продуктивності, що перевищувала 15 MIPS (мільйонів інструкцій, виконуваних в секунду). Почувши про один бите введення-виведення на кожну інструкцію, дослідники з лабораторії ім. Лоуренса в Ліверморі засумнівалися в достовірності цих відомостей, але тести, які виконувались на протязі місяця, показали, що в робочий час, коли користувачі зверталися до машин зі своїх консолей, число бітів введення-виведення становило в середньому 1,1, а по ночах, при виконанні операцій пакетної обробки, середнє значення дорівнювало 1,0. Результати всіх здивували, але ні вони, ні я не розуміли, звідки взялося це значення. Коли віртуальна пам'ять стала використовуватися повсюдно, число бітів введення-виведення, що припадає на кожну інструкцію, дедалі менший. Обсяг наявних у мене даних вельми обмежений, але я цілком обгрунтовано припускаю, що пов'язано це зі зменшенням розмірів програм, які більше не потрібно було повністю тримати в пам'яті під час виконання.
закон Амдала
У 1967 році мене попросили підготувати доповідь [3] для конференції Spring Joint Computer Conference, що проходила на східному узбережжі. Було потрібно порівняти обчислювальний потенціал комп'ютера, оснащеного одним потужним процесором, з унікальним квазіпараллельний комп'ютером ILLIAC (Illinois Integrator and Automatic Computer) IV [4] , Який на конференції повинен був представляти Деніел Слотнік.
Комп'ютер ILLIAC IV (рис.1) мав єдиний блок обробки команд (I-unit), який керував 16 блоками виконання арифметичних операцій (E). Кожен блок E мав власну схему адресації даних і самостійно визначав, чи повинен він брати участь у виконанні поточної інструкції I-unit, - цікаве, але спірне рішення. Комп'ютер з єдиним процесором представляв собою не конкретну машину, а якийсь архітектурний тип, і мені треба було оцінити, який продуктивності можна домогтися за такою конструкцією. На рис. 2 показана діаграма зростання продуктивності ILLIAC IV при вирішенні завдань з варіюється, але досить раціональною ступенем паралелізму, керованої ОС. На рис. 3 те ж завдання виконується на суперскалярного процесорі.
На рис. 4 показана очікувана продуктивність ILLIAC IV після інтеграції Слотника 256 арифметичних блоків і рішення задач з різним ступенем паралелізму, яка перевищувала б рівень, відповідний «символу чистоти Америки» (згадаємо рекламу мила Ivory, «чистого на 99,4%»). Для оцінки продуктивності ILLIAC IV я вивів формулу, в якій передбачається, що при наявності паралелізму задіяні можуть бути всі процесори:
Чисельник формули Rsх (S + P) і знаменник - S + P / 16 відповідають архітектурі ILLIAC IV, яка була запропонована в 1967 році і мала 16 арифметичних блоків. У цій формулі S - це частина завдання, яка вирішується шляхом послідовного виконання операцій, а P - частина завдання, яке вирішується паралельно (при наявності у комп'ютера такої можливості). Сума (S + P) - це сукупна робоча навантаження (W). Rs - продуктивність комп'ютера, який виконує операції послідовно (незважаючи на можливість їх розпаралелювання), що збігається зі швидкістю блоку команд (I-unit) ILLIAC IV. Знаменник відображає здатність ILLIAC IV вирішувати частину P в 16 разів швидше (повне завантаження потужностей ILLIAC IV відбувається тільки при виконанні векторних або матричних операцій, які можна распараллелить на 16 і більше потоків). Співвідношення (S + P) / (S + P / 16) характеризує можливості збільшення продуктивності ILLIAC IV при паралельному виконанні операцій. До речі, ніхто так і не оскаржив цю формулу, хоча підвищення продуктивності при паралельних обчисленнях лише в півтора рази багато хто вважав занадто низьким. Цей показник трохи відрізняється від того, що я привів в 1967 році під час своєї доповіді [3], і я не розраховував на те, що він буде зберігати свою актуальність протягом довгого часу. Я ніколи не називав цю формулу «законом Амдала» і багато років про неї взагалі не чув, розглядаючи її лише як верхня межа продуктивності для комп'ютера, що має один блок команд і n арифметичних блоків. Я лише хотів акцентувати увагу на недоліках операційних систем того часу.
Двадцять років по тому мені повідомили, що команда дослідників з національної лабораторії Сандия спростувала закон Амдала. Вони використовували нову на той момент паралельну машину з розподіленою пам'яттю. Групи обчислювальних вузлів з'єднувалися один з одним, а кожен вузол при цьому був пов'язаний з пристроями введення-виведення, призначеними для завантаження операційної системи, введення вихідних даних і виведення отриманих результатів. Все управління і переміщення даних здійснювалося паралельно. Я не став вплутуватися в суперечку, вказавши лише, що моя формула описувала цілком конкретну архітектуру комп'ютера ILLIAC IV, у якого був лише один блок команд. Закон Амдала використовувався також при проектуванні багатомашинних систем, що розроблялися компанією Massively Parallel. Головний конструктор компанії враховував мою формулу при подальшому розширенні своєї системи, а я в підсумку отримав запрошення увійти до ради директорів цієї компанії.
***
Представлені мною результати ніколи не претендували на роль універсального закону - я всього лише шукав зв'язок між обсягом пам'яті і продуктивністю комп'ютера і аналізував відношення кількості бітів введення-виведення до числа виконаних інструкцій, розглядаючи це як функцію від тієї частини програми, яка повинна знаходитися в віртуальної пам'яті . В кінцевому підсумку все розчинилося в імлі минулих років. Головним же своїм досягненням я вважаю архітектуру WISC, яку мені вдалося створити фактично з нуля.
література
- J. von Neumann, First Draft of a Report on the EDVAC. Moore School of Electrical Eng., Univ. Pennsylvania, 30 June 1945; URL: www.virtualtravelog.net/wp/wp-content/media/2003-08-TheFirstDraft.pdf (Дата звернення: 11.02.2014).
- PN Edwards, Chapter 3: SAGE, The Closed World: Computers and the Politics of Discourse in Cold War America. MIT Press, 1996, P. 76-114.
- GM Amdahl, Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities. Proc. AFIPS Conference, AFIPS Press, 1967, P. 483-485.
- GH Barnes et al., The ILLIAC IV Computer. IEEE Trans. Computers, vol. C-17, no. 8, 1968, P. 746-757.
- JL Gustafson, Reevaluating Amdahl's Law. Comm. ACM, vol. 31, no. 5, 1988, P. 532-533.
Джин Амдал почав свою кар'єру в корпорації IBM в 1952 році, був провідним розробником комп'ютера IBM 704, очолював напрямок проектування архітектури і потоків даних сімейства IBM 360. У 1965 році Амдал був удостоєний звання «Почесний співробітник IBM» (IBM Fellow) і до 1970 року керував роботою лабораторії IBM Advanced Computing Systems Laboratory в Менло-Парк, де і заснував компанію Amdahl Corporation. Діяльність доктора Амдала відзначена численними нагородами і патентами.