Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ

няет текст. Для реализации языка

обычен компилятор, транслирую-

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

загрузочный модуль.

3. Редактор связей — специальная программа, обеспечивающая возмож-

ность работы загрузочного модуля совместно с другими программами

данной операционной среды. В ряде случаев (например, в ОС

UNIX

) ре-

дактор связей не требуется,поскольку решение соответствующих задач

возлагается на операционную систему.

4. Стандартная библиотека, которая объединяет в себе библиотеки пе-

риода трансляции (статические библиотеки)и периода исполнения (ди-

намические библиотеки).

5. Отладчик — программа, обеспечивающая отслеживание хода вычи-

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

диалога. Обычной для

и для большинства других систем программи-

рования является организация отладки, которая связывает шаг испол-

нения со строкой исходного текста.

§ 1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫ-

КИ

Из материалов предыдущего раздела видно, что подходы к решению про-

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

от друга. Иногда эти различия значительны, иногда сводятся лишь к тексто-

вому представлению программы, а потому их можно считать непринципи-

альными. Если различия считаются непринципиальными, то мы говорим о

том, что языки имеют сходную модель вычислений.

В дальнейшем мы часто будем пользоваться термином “традиционные

языки”, понимая под этим языки, модель вычислений которых унаследована

от так называемой архитектуры фон Неймановского типа, принятой в пода-

вляющем большинстве существовавших и существующих вычислительных

машин. Эта архитектура характеризуется следующими принципами:

1. Наличие трех элементов вычислительной системы:

(a) память, которая предназначена для хранения произвольных зна-

чений. Значения на аппаратном уровне представляются как после-

довательности битов;

ГЛАВА 1. ПОНЯТИЯ

(b) процессор, который способен выполнять команды, т. е. интерпре-

тировать последовательности битов как инструкции для активи-

зации предписываемых этими инструкциями действий;

рые должен выполнять процессор (иногда управляющее устрой-

ство рассматривается как составная часть процессора).

2. Однородность памяти и адресация. Память машины рассматрива-

ется как вектор, состоящий из одинаковых ячеек, способных прини-

мать (от процессора) любые значения.Значение в ячейке с точки зрения

процессора является последовательностью битов фиксированной дли-

ны без каких бы то ни было ограничений. Ячейки памяти идентифи-

цируются адресами: числами от нуля до максимально возможной для

данной машины величины (обозначающей последнюю ячейку), Адреса

служат указателями для процессора, откуда следует извлекать значение

или куда помещать значение.

Из однородности памяти следует, что команды и данные (перерабаты-

ваемые значения) располагаются в единой общей памяти и одинаково

адресуются.

3. Пассивность памяти и активность процессора. Ячейка памяти все-

гда содержит какое-то значение. Полученное ячейкой значение не мо-

жет быть изменено иначе как при выполнении специальной команды

процессора, предназначенной для этого действия, — команды засыл-

ки, или присваивания значения. Изменяемая ячейка указывается своим

адресом.

Процессор всегда выполняет некоторую команду, закодированную по-

следовательностью битов в ячейке и извлеченную из памяти. Команды

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

ячеек, над которыми выполняются предписываемые действия. Именно

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

интерпретирует значение ячейки-операнда как число, символ, адрес в

памяти и др. Число операндов команды называется ее адресностью,

а адресность большинства команд — адресностью машины. Различа-

ются одно-, двух- (и в настоящее время реже) трехадресные машины и

машины с нефиксированной адресностью.

4. Роль устройства управления.Управляющее устройство содержит адрес

1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ

команды, назначаемой для выполнения процессором. Если эта коман-

да является командой передачи управления, т. е. при ее выполнении

определяется адрес ячейки, содержащей команду, которая должна вы-

полняться после текущей, то этот адрес становится новым содержи-

мым устройства управления.В противном случае,адрес команды,кото-

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

кущее содержимое устройства управления, увеличиваемое на единицу

(т. е. очередная выполняемая команда содержится в ячейке памяти, сле-

дующей за текущей). Таким образом, управляющее устройство мож-

но моделировать как регистр, называемый счетчиком команд. Этот ре-

гистр модифицируется автоматически либо командами передачи упра-

вления. Такой взгляд часто полезен программисту при разработке ин-

терпретирующих программ, когда ему нужно промоделировать переда-

чи управления.

5. Наличие канала связи между памятью и процессором. Для пере-

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

емой какой-либо командой, используется специальное оборудование,

называемое каналом связи.Работа канала осуществляется в следующих

случаях:

(a) когда требуется подать для выполнения процессором очередную

команду (активизируется управляющим устройством),

(b) когда для выполнения команды процессору требуется получить

операнд (активизируется процессором),

ки (активизируется процессором).

Конкретная схема канонической фон Неймановской машины дополняется

устройствами ввода и вывода данных, активизация которых осуществляется

при выполнении соответствующих команд процессором (возможны различ-

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

связь с памятью автономная, через процессор или через специальную шину

данных и др.).

На рис. 1.1 показано взаимодействие частей фон Неймановской вычисли-

тельной машины. Сплошными стрелками отмечена передача информации по

каналу (двунаправленные стрелки — передача в оба направления). Пунк-

тирные стрелки обозначают действия с управляющим устройством, которые

ГЛАВА 1. ПОНЯТИЯ

осуществляются в связи с исполнением команды

К О1 О2

, размещенной в па-

мяти по адресу 3: непосредственно до нее (запрос управляющего устройства

кода команды по адресу 3) и после нее (указание на необходимость запроса

команды, следующей в памяти за исполняемой).

Канал связи

Процессор

Память

Управляющее

устройство

К О

Рис. 1.1. Схема выполнения двухадресной команды на фон Неймановской

машине

Классическая схема сформировалась под давлением требования миними-

зировать части системы, критичные к сбоям оборудования, поскольку суще-

ствовавшая в середине XX века техническая база не позволяла решать задачу

надежности в должной мере. В результате только процессор можно назвать

активным устройством машины. По этой же причине выбран довольно при-

митивный способ управления: переход к следующей команде или к команде

1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ

по принудительно задаваемому адресу. К тому же неразвитость отрасли в

целом не позволяла даже ставить задачу повышения эффективности вычи-

слений за счет выбора подходящей модели вычислений.

По мере накопления опыта работы с вычислительными машинами появи-

лась потребность увеличения быстродействия процессора и объемов памяти.

И очень скоро выяснилось, что каноническая схема фон-неймановских вы-

числений препятствует повышению производительности. По этой причине

сегодня эта схема всегда модифицируется. Ниже приведены некоторые, но

довольно характерные модификации схемы:

a) У процессора появляются собственные ячейки со специальной адресаци-

ей, не требующие обращения к памяти. С их помощью можно уменьшать

адресность команд машины, передавать промежуточные результаты вы-

числений от команды к команде, выполнять иные локальные действия.

Они называются быстрыми регистрами процессора.

b) Уменьшается размер команд, в частности, их адресность. Наиболее упо-

требляемые действия кодируются короткими последовательностями би-

тов, отдается предпочтение одноадресным командам (это возможно бла-

годаря регистрам процессора).

c) Команды кодируют довольно сложные действия над операндами, которые

объединяют наиболее часто употребляемые последовательности элемен-

тарных операций.

d) Процессор снабжается памятью для команд, которые вероятно будут вы-

полняться после текущей команды (эта память,называемая кэшем команд,

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

которой дублируются значения основной памяти с целью обеспечить сле-

дующие команды операндами (кэш данных).

e) Память разбивается по уровням доступа: регистры процессора, область

быстрого доступа с непосредственной адресацией, область,адресация ко-

торой требует предварительного указания некоторого сегмента, ячейки

которого адресуются непосредственно,и т. д.Другой вариант той же идеи —

возможность переключения с сегмента на сегмент с сохранением более

медленного доступа к ячейкам вне текущего сегмента.

Полезность подобных модификаций очевидна. Однако есть причина, из-за

которой возможности роста эффективности фон Неймановских вычислений,

ГЛАВА 1. ПОНЯТИЯ

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

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

приводит к росту скорости счета лишь в тех пределах, которые определе-

ны скоростью канала связи между процессором и памятью: если она невы-

сока, то процессор будет все равно простаивать, ожидая очередной коман-

ды, операндов или окончания выполнения присваивания

. В свою очередь,

рост скорости канала связи ограничен из-за постоянно растущей потребно-

сти расширения объема памяти. На эти принципиально непреодолимые огра-

ничения классической модели вычислений указал Бэкус еще в середине се-

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

(буквально bottleneck) модели фон Неймана. Уместно заметить, что много-

процессорность, а тем более кэширование и прочие модификации канони-

ческой модели являются лишь полумерами, позволяющими расширить, но

никак не ликвидировать узкое место (впервые это было отмечено в лекции

Бэкуса [82]).

В качестве альтернативы фон Неймановской модели укажем лишь на од-

ну из идей радикально новой модели, реализация которой позволяет значи-

тельно обогатить возможности параллельного счета. Для достижения парал-

лельности действий увеличивается активность элементов вычислительной

системы и изменяются принципы управления вычислениями.

Идея заключается в том, чтобы разрешить выполнение всех команд, для

которых к данному моменту готовы операнды (вычислены их значения). Цен-

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

кого распараллеливания вычислений, если оборудование обеспечит факти-

чески одновременное выполнение готовых команд. Прямое развитие данной

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

и наиболее очевидный из конфликтов синхронизации — попытка одновре-

менной записи результатов нескольких команд в одну ячейку памяти. Поэто-

му присваивания становятся тормозом на пути программирования. Более то-

го, можно теоретически предвидеть (хотя точной оценки еще не было сдела-

но;впрочем,даже там,где такие оценки имеются, они игнорируются и замал-

чиваются), что распараллеливание программ, написанных в традиционном

стиле — мартышкин труд

. Стиль программирования можно корректировать

Иллюстрацией интенсивности работы канала фон Неймановской машины может служить

схема выполнения команды на рис. 1.1, которая показывает, что для выполнения двухадрес-

ной команды

К О1 О2

требуется шесть обращений к каналу.

И. Н. Скопин. Я считаю этот эпитет слишком сильным, но соавтор не согласился смяг-

1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ

различными способами, например, путем замены хранения результата пере-

дачей его в качестве операндов ранее заблокированным командам, которые

тем самым активизируются. Какие элементы оборудования будут выполнять

такие команды, на уровне идеи не имеет значения — это задача техническая

(т. н. задача динамической коммутации).

Здесь стоит обратить внимание на два взаимосвязанных момента. Во-пер-

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

следствие,потребность в пассивной памяти существенно снижается. Во-вто-

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

мают на себя элементы оборудования, отвечающие за выяснение готовности

команд к выполнению. Это — одна из схем, которая подчиняет управление

потокам данных (data ﬂow). Такие схемы противопоставляются управляю-

щим потокам (control ﬂow) фон Неймановских вычислений.

Представленная идея неоднократно воплощалась в оборудовании (т. н.

машины потоков данных). Но каждый раз узким местом для таких машин

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

лям, к которым привыкли программисты. Как следствие, в каждом из таких

процессоров делались грубые системные ошибки, приводившие к затрудне-

ниям в программировании, а также к понижению скорости и гибкости вычи-

слений. Тем не менее, поскольку скорость света очень скоро поставит предел

механическому увеличению пропускной способности каналов, к подобным

схемам придется вернуться на другом уровне.

Одной из сторон машин потоков данных является повышение активно-

сти памяти, в которой размещаются команды и их операнды. По этому пути

можно пойти еще дальше, сделав всю память активной. В этом случае, во из-

бежание полной анархии, обычно память имеет общее устройство управле-

ния, задающее одну команду (или несколько команд, в зависимости от како-

го-то очень быстро проверяемого условия), которую выполняют все ячейки

(ассоциативная память). История реализации этой идеи аналогична исто-

рии машин потоков данных: аппаратные предпосылки есть, но эффективных

способов программирования нет.

История с ассоциативной памятью и машинами потоков данных показы-

вает, что,несмотря на очевидные преимущества для отдельных классов задач

других моделей вычислений и на очевидную неэффективность классической

модели вычислений, не происходит переход к другим более перспективным

с точки зрения ускорения счета моделям. Почему? Это очень непростой во-

чить его.

ГЛАВА 1. ПОНЯТИЯ

прос, связанный как со сложившимися традициями, так и с огромным грузом

накопленного программного обеспечения. В частности, другие модели вы-

числений очевидно неуниверсальны, ориентированы на некоторые классы

задач, а иллюзия универсальности, основанная на примитивно истолкован-

ной теореме об универсальном алгоритме, сопутствует традиционной моде-

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

сегодняшняя армия программистов воспитана на фон Неймановской модели,

и она уже не в состоянии перестроиться.Одна из причин тому —так называе-

мые традиционные языки, ключевые средства которых “выросли” из модели

фон Неймана. Эти языки стали основой для выработки наиболее употребля-

емых стилей программирования

. Ниже перечислены особенности языков,

которые унаследованы от фон Неймановской модели вычислений:

a) Присваивание значений. Языковая конструкция, предназначенная для ло-

кального запоминания результата вычислений, получившее название опе-

ратора присваивания значения переменной, или засылки значения,— пря-

мой потомок передачи значения по каналу связи от процессора к памяти.

В большинстве языков программирования понятие переменной практиче-

ски всегда рассматривается как аналог ячейки (или группы ячеек) памяти.

b) Операторы. Основной конструкцией действия в языке является опера-

тор. Выполнение одного оператора зависит от выполнения другого толь-

ко в том смысле, что более ранние вычисления могут менять память (со-

держимое некоторых ячеек), в контексте которой выполняются последу-

ющие операторы. Иными словами, зависимость операторов посредством

использования памяти в точности соответствует тому,что имеет место для

команд фон Неймановской машины.

c) Структура управления. Последовательное выполнение операторов, тек-

стуально следующих друг за другом, совершенно аналогично последо-

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

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

следующим, ничем не отличается от машинной команды безусловной пе-

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

В последующих разделах мы уделим особое внимание вопросам, связанным со стилями

программирования. Здесь же следует отметь, что универсального стиля программирования

не существует, и действительно квалифицированный программист не будет ограничивать

себя использованием какого бы то ни было, но одного стиля, он всегда стремится применять

средства, которые соответствуют решаемой задаче в максимальной степени.

1.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ ФОН НЕЙМАНА И ТРАДИЦИОННЫЕ ЯЗЫКИ

вычисления определяют, какой оператор будет выполняться следующим.

Способы указания групп операторов, выполнение или невыполнение ко-

торых зависит от некоторого условия (выражения, значения которого вы-

деляют соответствующие им группы), всего лишь фиксируют в языке ти-

повые приемы разветвления вычислений. Эти приемы есть образы наи-

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

манд.

d) Приведения. В традиционных языках обычным является употребление зна-

чения одного типа, которое присваивается переменной другого типа. Это

не только присваивание целого вещественной переменной, когда суще-

ствует “разумная” интерпретация целого как округленного вещественно-

го, или подобное преобразование в выражениях, но и неоднозначно трак-

туемые преобразования, смысл которых нельзя понять в отрыве от кон-

кретной программы. Автоматические приведения значений к типам, опре-

деляемым контекстом использования, — прямое следствие соглашения

об однородности памяти. И хотя в развитых языках программирования

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

факт их осуществимости считается чуть ли не достоинством языка.

e) Подпрограммы. Возможность объявлять некоторые последовательности

операторов отдельно от тех мест программы, в которых их требуется вы-

полнять, обозначать такие последовательности именами с тем, чтобы ука-

зывать эти имена в местах требуемого выполнения, — обычный прием

группировки команд в подпрограммах на машинных языках. Единствен-

ная разница здесь в том, что языки программирования более выразитель-

ны, что они (до известных пределов) позволяют абстрагироваться от того,

какие стандартизованные последовательности команд используются для

оформления подпрограммы и ее вызова для исполнения.

Если в архитектурах вычислительных машин отходят от принципов фон Ней-

мана преимущественно для повышения эффективности счета,то побудитель-

ных причин для нарушения канона при конструировании языков программи-

рования гораздо больше. Это и стремление к большей выразительности, и

уже упомянутая фиксация типовых приемов программирования, и помощь в

отыскании ошибок в программах.Наиболее часто нарушается принцип одно-

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

товки хранимых данных, что, в свою очередь, способствует и выразительно-

ГЛАВА 1. ПОНЯТИЯ

сти, и надежности программ

Для большинства существующих языков характерно, что программист

может (и должен!) думать о выполнении программы как о работе автомата,

имеющего активный процессор и пассивную память (возможно, разнород-

ную), связанные каналом. Появление в языке структуры памяти и так назы-

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

библиотек — это всего лишь повышение уровня абстрактного вычислителя

языка, который, тем не менее, трактуется как автомат фон Неймановского ти-

па, пусть даже с весьма сложными командами. Если язык предусматривает

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

то мы называем этот язык нетрадиционным. С этой точки зрения такие со-

временные языки, как

С++

или

Ada

, остаются традиционными, а, к примеру,

такой “патриарх языкотворчества”, как

LISP

— нетрадиционен.

Данное разграничение традиционных и нетрадиционных языков нельзя

рассматривать в качестве точного определения. Достаточно развитый язык

позволяет выражать алгоритмы в разных стилях, и программист может себе

позволить строить тексты программ (фрагментов программ) в соответствии с

особенностями решаемой задачи, отходя от тех правил,которые поддержива-

ются явно языком. Но если в языке не хватает возможностей, адекватных для

такого построения, а это, вообще говоря, обычная ситуация, то приходится

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

Когда при этом требуется забота об эффективности, а это опять-таки обыч-

но, необходимо учитывать реалии конкретного компьютера. Как следствие,

весьма вероятны нарушение адекватности моделирования и потеря нагляд-

ности решения.

В заключение настоящего раздела приведем перечень (далеко не полный!)

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

большими комментариями.

1. FORTRAN. Самый почтенный долгожитель среди языков программи-

Как уже отмечалось, отклонение от принципа однородности памяти для повышения эф-

фективности используется и в оборудовании. Сегментация, быстрые регистры, кэширова-

ние — далеко не единственные решения этого плана. Нарушение принципа здесь лишь ча-

стичное: ячейка любого из видов по-прежнему способна принимать значения разного типа,

по-прежнему смысл значения раскрывается только процессором. Заслуживают упоминания

и более радикальные архитектуры, предусматривающие тегирование (см. стр. 62), а также

полное отделение в памяти областей, в которые можно записывать данные и команды (в

обычном режиме выполнения программ процессору не разрешается записывать что-либо в

область команд, в результате повышается надежность программ).