В 1950-х годах программирование только начинало оформляться как профессия. Компьютеры были огромными, дорогими и медленными, а программистам приходилось вручную расписывать каждую операцию — часто на уровне, близком к машинному коду. Но находились люди, которые задавались вопросом: а можно ли сделать так, чтобы компьютер сам оптимизировал свою работу?
Одним из таких людей была Фрэнсис Аллен. Она начинала как учительница математики и вообще не планировала связывать жизнь с программированием, но смогла изменить представление всех о том, как должны работать компьютеры.
Ферма, школа и математика
Фрэнсис Элизабет Аллен родилась 4 августа 1932 года и выросла на молочной ферме в Перу в штате Нью-Йорк, недалеко от озера Шамплейн. Она была старшим ребенком в семье фермера и школьной учительницы. Начальное образование она получила в школе с одной комнатой, расположенной в миле от дома, а затем посещала местную среднюю школу. В 1954 году она окончила Педагогический колледж штата Нью-Йорк (ныне часть Университета Олбани) со степенью бакалавра по математике и вернулась в родной город, чтобы преподавать в школе.
Ее вдохновляла мать, которая была учительницей начальных классов, и любимый учитель математики. Аллен проработала в школе два года, но для полной сертификации ей требовалась степень магистра. Она поступила в Мичиганский университет, где в 1957 году получила степень магистра по математике. Именно там она впервые столкнулась с программированием — один из первых курсов по этой дисциплине только начинал читаться. Однако обучение в магистратуре стоило дорого, и, чтобы оплатить его, Аллен взяла студенческие займы. К моменту выпуска она была должна значительную сумму, которую не могла быстро погасить с учительской зарплаты.
Именно эти долги и привели ее в IBM. В 1957 году компания как раз набирала программистов, и Аллен прошла собеседование прямо в кампусе Мичиганского университета. Она согласилась на работу, планируя остаться там лишь до тех пор, пока не расплатится с займами, а затем вернуться к преподаванию — профессии, которую, по ее собственным словам, знала и любила.
«Одноразовая работа» длиною в 45 лет
В июле 1957 года, обремененная студенческими займами, Аллен пришла в исследовательское подразделение IBM в Покипси в штате Нью-Йорк на должность программиста. Она планировала остаться там ровно до тех пор, пока не расплатится с долгами, однако этим планам не суждено было сбыться.
Ее первым заданием стало обучение научных сотрудников IBM языку FORTRAN, который компания анонсировала всего за два-три месяца до ее прихода. Чтобы разобраться в том, как работает компилятор FORTRAN, Аллен прочитала его исходный код. Это положило начало ее пожизненному интересу к компиляторам. Фрэнсис называла эту работу «одноразовой», но она оказалась настолько увлекательной, что Аллен осталась в IBM на 45 лет, вплоть до выхода на пенсию в 2002 году.
В IBM она прошла путь от программиста до одного из ведущих исследователей в области компиляторов. В 1989 году она стала первой женщиной, удостоенной звания IBM Fellow — высшего технического отличия компании, а в 1995 году — избрана президентом Академии технологий IBM.
За свою карьеру Фрэнсис работала над компиляторами для суперкомпьютера IBM 7030 Stretch и для системы Harvest, созданной для взлома кодов в Агентстве национальной безопасности США.
Пионер оптимизирующих компиляторов
Главный вклад Аллен в компьютерную науку связан с оптимизирующими компиляторами — программами, которые переводят код, написанный человеком, в машинные инструкции и при этом делают его более эффективным. К слову, первый в мире компилятор за полтора десятилетия до этого создала другая женщина — Грейс Хоппер. Но если Хоппер решала задачу самого перевода, то Аллен пошла дальше: ее интересовало, как сделать переведенный код не просто рабочим, а быстрым и компактным.
В начале 1960-х годов компиляторы создавали код, который был значительно медленнее и объемнее того, что могли написать программисты, работающие напрямую с машинными кодами. Аллен вместе с Джоном Коком и командой IBM создала оптимизирующий компилятор, который генерировал код, достойный возможностей железа. Ее статья 1966 года «Program Optimization» заложила концептуальную основу для систематического анализа и преобразования программ.
В ней Аллен предложила использовать графовые структуры для кодирования содержимого программы — то есть представить код в виде схемы, где узлы — это отдельные операции или блоки команд, а связи между ними показывают, как управление переходит от одного шага к другому. Такая «карта» программы позволяла компилятору автоматически находить места, которые можно переписать более эффективно, не теряя логики.
В статье 1970 года «Control Flow Analysis» Аллен развила методы анализа потока управления программой, используя графовые структуры и отношения между блоками кода, включая доминирование. «Интервалы» позволяли разбивать сложную схему программы на вложенные области, а «доминирование» помогало определить, какие блоки кода всегда выполняются перед другими — без этого невозможно было понять, где находятся циклы и какие операции можно безопасно переставить или объединить. Это был важный шаг вперед по сравнению с более ранними абстракциями, которые не позволяли автоматизировать анализ на таком уровне.
А в 1971 году совместно с Коком Аллен опубликовала «A Catalog of Optimizing Transformations» — первый систематизированный каталог оптимизационных преобразований. В нем были описаны конкретные приемы, которые компилятор может применять к программе. Например, свертка констант — когда выражения вроде 2 + 3 вычисляются еще на этапе компиляции и заменяются готовым результатом 5, чтобы не тратить время на это во время работы программы.
Именно эти работы заложили теоретическую и практическую базу для современных оптимизирующих компиляторов. Аллен разработала и внедрила свои методы в компиляторах для IBM STRETCH-HARVEST и экспериментальной системы Advanced Computing System, доказав жизнеспособность и структуру современных машинно- и языково-независимых оптимизаторов.
Параллельное выполнение: PTRAN и граф зависимостей
В 1984 году Аллен основала и возглавила проект PTRAN (Parallel TRANslator) — исследовательскую группу, изучавшую, как автоматически распараллеливать последовательные программы на FORTRAN для выполнения на многопроцессорных системах. В то время параллельные вычисления только начинали развиваться, и вопрос о том, как автоматически находить в программах части, которые можно выполнять одновременно, был открыт.
Команда PTRAN разработала новые схемы обнаружения параллелизма и создала концепцию графа зависимостей программы (program dependence graph) — основного метода структурирования, который до сих пор используется большинством распараллеливающих компиляторов. Под руководством Аллен PTRAN стал одним из заметных исследовательских проектов IBM в области автоматического распараллеливания программ.
Вклад Аллен в автоматическое распараллеливание имел огромное значение для высокопроизводительных вычислений. Ее работа позволила программам использовать несколько процессоров одновременно для получения более быстрых результатов — это стало основой для решения таких задач, как прогнозирование погоды, сопоставление ДНК и функции национальной безопасности.
Первая женщина — лауреат премии Тьюринга и наставничество
В 2007 году Фрэнсис Аллен была удостоена премии Тьюринга — высшей награды в области компьютерных наук, которую часто называют «Нобелевской премией по информатике». Она стала первой женщиной, получившей эту награду с момента ее учреждения в 1966 году.
Премия была вручена в феврале 2007 года и включала денежное вознаграждение в размере $100 000. Председатель комитета по присуждению премии Рузена Баичи отметила, что работа Аллен привела к замечательным достижениям в проектировании компиляторов и архитектуре машин, которые лежат в основе современных высокопроизводительных вычислений. Она также подчеркнула символичность того, что Аллен работала над секретными кодами для Агентства национальной безопасности, поскольку именно Алан Тьюринг, в честь которого названа премия, разрабатывал методы взлома немецких кодов во время Второй мировой войны.
Помимо премии Тьюринга, Аллен была удостоена множества других наград, включая Computer Pioneer Award от IEEE Computer Society в 2004 году за «пионерскую работу, установившую теорию и практику оптимизации компиляторов». В 2000 году IBM учредила награду имени Фрэнсис Э. Аллен для женщин в технологиях, и она стала ее первой обладательницей. В 2004 году она также получила первую награду Anita Borg Award for Technical Leadership.
Фрэнсис Аллен запомнилась и как наставник и защитник женщин в компьютерных науках. Коллеги описывали ее как доброго и воодушевляющего руководителя. Она активно участвовала в работе организаций, продвигающих женщин в технологии, включая Институт Аниты Борг и Национальный центр женщин и информационных технологий. После выхода на пенсию в 2002 году она осталась в IBM в статусе Fellow Emerita и продолжала работать в профессиональных организациях, чтобы увеличить роль женщин в вычислениях.
Аллен скончалась 4 августа 2020 года, в свой 88-й день рождения, от осложнений болезни Альцгеймера. Ее наследие живет в каждом современном компиляторе, который оптимизирует код, и в каждом параллельном вычислении, которое ускоряет работу программ. В 2020 году IEEE учредил новую медаль имени Фрэнсис Э. Аллен, спонсируемую IBM, чтобы отметить ее вклад в развитие вычислений.
История Фрэнсис Аллен — это история о том, как случайная работа может стать делом жизни. Она пришла в IBM, чтобы расплатиться по долгам, а осталась на 45 лет, потому что нашла в компиляторах то, что захватило ее ум. Она не планировала становиться пионером, но ее работы по оптимизации и распараллеливанию стали фундаментом, на котором построены современные высокопроизводительные вычисления. И она стала первой женщиной, получившей высшую награду в своей области, — не потому, что стремилась к этому, а потому, что просто делала свою работу хорошо.
Читайте также:
- Невидимая создательница компьютерной эпохи: история Джин Бартик.
- Как создавался Google и причем тут Lego и платье Дженнифер Лопес.
- Как человек, который изобрел интернет, мог бы владеть им, но отдал его миру бесплатно.
- Человек, который придумал компьютер, но не смог его построить: история Чарльза Бэббиджа.