close

Вход

Забыли?

вход по аккаунту

?

FreeBASIC4

код для вставкиСкачать
Пособие для начинающих программировать на языке высокого уровня FreeBASIC. Работа состоит из нескольких глав. Фрагмент 4 "Алгоритмы вокруг нас" содержит дополнения к предыдущим "Фрагментам", связанные с замечаниями читателей. Для учащихся школ, ст
 1
Евгений Рыжов, инженер
Программирование на языке FreeBASIC
пособие для начинающих
Пособие для начинающих программировать на языке высокого уровня FreeBASIC.
Работа состоит из нескольких глав. Фрагмент 4 "Алгоритмы вокруг нас"
содержит дополнения к пре
дыдущим "Фрагментам", связанные с замечаниями
читателей. Для учащихся школ, студентов институтов, а также преподавателей.
Фрагмент 4. Алгоритмы вокруг нас.
Вопрос.
Д
-
р Винер, существует ли опасность, что машины –
вычислительные машины –
когда
-
нибудь
возьмут верх над людьми?
Ответ.
Такая опасность, несомненно, существует, если мы не усвоим реалистического взгляда на вещи. Собственно говоря, это опасность умственной лени. Некоторые так сбиты с толку словом "машина", что не представляют себе, что можно и чего нельзя делать с машинами и что можно и чего нельзя оставить человеку.
2
Вопрос.
Эти машины будущего отнимут еще много занятий у людей?
Ответ.
Отнимут.
Вопрос.
Это обострит проблему, которая уже существует. Где же решение?
Ответ.
Ответ гласит: мы больш
е не можем оценивать человека по той работе, которую он выполняет. Мы должны оценивать его как человека. В этом суть. Вся уйма работы, для которой мы сейчас используем людей –
это работа, в действительности делаемая лучше машинами.
Норберт Винер
Интервью
для
журнала
"U.S. News & World Report", 1964
Норберт Винер (Norbert Wiener; 1894 —
1964)
По просьбе читателей хочу сделать несколько дополнений.
Дополнение №1.
К Фрагменту 3. Некое техническое устройство.
Раздел 2.2.2. Некоторые важные "вехи".
Исто
рия британского "Колоссуса" (
"Колосс"
) началась в 1940, когда спецгруппа английской полиции, прослушивавшая радиоэфир для поиска германских шпионов на территории острова, случайно отловила шифрованную немецкую радиопередачу необычного вида. Основная секрет
ная переписка Третьего рейха велась с помощью шифратора "Энигма"
(в годы войны использовалось около 200 тыс. таких аппаратов). Но для телеграфной радиосвязи Гитлера и генштаба с командованием армий использовалась более серьезная машина фирмы "Лоренц". Эта приставка к телепринтеру имела размеры 51х46х46 см и получила название "Lorenz SZ 40" (SZ –
Shlusselzusatz –
Шифрприставка). Телепринтер давал текст в коде Бодо: 5 перфорационных дорожек с информацией плюс еще одна дорожка синхронизации со сплошной перфора
цией. Каждый знак текста представлен 5 битами, по одному на каждой из 5 дорожек. На каждый такт выхода телепринтера шифрприставка выдавала свою группу из 5 псевдослучайных бит, которые в сумматоре побитно складывались со знаком исходного текста операцией X
OR.
3
Британская машина "Колосс"
Дополнение №2.
К Фрагменту 3. Некое техническое устройство.
Раздел 2.2.2. Некоторые важные "вехи".
Компьютеростроение в Британии продолжилось и в послевоенные годы –
пример тому старейший компьютер "Harwell Dekatron"
(Ха
руэлле компьютер).
Внешний вид машины "Harwell Dekatron"
4
Строительство началось в 1949, машина стала функционировать в апреле 1951. Характерная черта, отраженная в названии -
энергонезависимая память машины (ОЗУ) была построена на декатронах
, для ввода
и хранения программ использовалась бумажная лента. Машина была десятичной, для представления данных использовались 8
-
разрядные регистры.
Многоэлектродная газоразрядная лампа "декатрон"
Машина в течение шести лет использовался для проведения расчетов в центре исследования атомной энергетики Великобритании. В 1957 "Harwell Dekatron" был отправлен в технический колледж города Вулвэрхэмптон, где использовался, как учебное пособие на протяжении нескольких десятилетий. Всего в конструкцию "Harwell Dekatron"
входит 828 декатронов, 131 лампа других типов, 480 обычных и 26 высокоскоростных реле, а также 199 индикаторных ламп и 18 коммутаторов. Компьютер размещается в стойке размерами 2 х 6 х 1 м, весит 2,5 т и потребляет мощность 1,5 кВт.
В 1973 машина попала в Книгу Рекордов Гиннеса
, как самый прочный компьютер. 20 ноября 2012
"Harwell Dekatron" снова заработал, пополнив экспозицию Национального музея вычислительной техники в Блетчли
-
Парке. Особняк Блетчли
-
Парк находится в городе Блетчли, расположенном в графс
тве Бакингемшир в центре Англии. В годы Второй мировой войны здесь дислоцировалась правительственная Школа кодов и шифров (Government Code and Cypher School) —
главная шифровальная служба Великобритании.
Дополнение №3.
К Фрагменту 3. Некое техническое уст
ройство.
Раздел 1.2. Об "информационных" машинах можно говорить долго...
Не пропустили читатели и замечание Анатолия Алексеевича Дородницына
о важности третьей, алгоритмической части информатики -
"brainware". По
-
сути это и дало толчок к написанию статьи "Фрагмент 4. Алгоритмы вокруг нас".
Среди разнообразных правил, с которыми приходится сталкиваться ежедневно и ежечасно, особую роль играют правила, предписывающие последовательность действий, ведущих к получению некоторого необходимого результата. Нередк
о их называют алгоритмами. С научной точки зрения к этому названию нужно добавить слова "в интуитивном смысле"... Интуицией называют знание, приобретенное в результате обширного опыта, но еще не подвергнутое научному анализу и потому недостаточно четкое и строгое. По мере накопления опыта это знание обогащается, и 5
потому наши интуитивные представления о чем
-
нибудь могут постепенно изменяться.
Эти слова принадлежат Н.А. Криницкому...
Николай Андреевич Криницкий (1914
-
1993)
Криницкий родился в 1914 году. В
1939 окончил механико
-
математический факультет МГУ и в 1940 был призван в ряды Красной Армии. Годы войны провел на фронте. Полковник в отставке, имеет боевые награды. После войны был преподавателем Военной Инженерной Артиллерийской Академии. Активно участ
вовал в формировании ВЦ № 1 Министерства Обороны, где плодотворно работал с 1955 по 1971 год. Далее, в течение 10 лет был заместителем начальника ГВЦ Госплана СССР. До последних лет жизни работал заведующим кафедрой и профессором МИРЭА.
Н.А.Криницкий был з
аместителем главного редактора журнала "Программирование" в течение 15 лет с момента основания журнала и членом редколлегии до последних своих дней. Сфера научной деятельности Н.А.Криницкого отличается большой широтой. В числе более 200 опубликованных рабо
т —
работы по теории алгоритмов, теории программирования, алгоритмическим языкам, информационным системам, интеллектуальным системам, формализации описания ЭВМ.
Н.А.Криницкому принадлежит первая общедоступная отечественная монография по программированию. А
книга А.И.
Китова и Н.А.
Криницкого "Электронные цифровые машины и программирование", первая в СССР общедоступная и на то время всеобъемлющая (без малого шестьсот страниц текста), книга
-
энциклопедия по ЭВМ и программированию была официально допущена Минис
терством образования СССР в качестве учебника для студентов и аспирантов университетов и вузов. По этой первой в СССР книге
-
учебнику училось несколько поколений программистов Советского Союза и ряда зарубежных стран.
Книгу Китов А.И.и Криницкий Н.А."Электр
онные цифровые машины и программирование"
. М., Физ
-
мат гиз., 1959. 572 с.
С сокращениями до 295 с. книгу можно посмотреть и скачать по ссылке:
http://www.computer
-
museum.ru/books/ecm_i_prog
.pdf
Алексей Андреевич Ляпунов (1911 —
1973)
Вместе с другими учениками А.А.Ляпунова Криницкий закладывал основы теоретического программирования, теории и практики построения информационных систем. Алексей Андреевич Ляпунов (1911 —
1973) —
выдающийся с
оветский математик, один из основоположников кибернетики, член
-
корреспондент АН СССР. Специалист в области теории функций вещественного переменного и математических вопросов кибернетики. По семейным преданиям род Ляпуновых берет начало от князя Константина
Галицкого, брата Александра Невского. Среди 6
представителей этого рода много ученых. Краткую их родословную
можно начать с Василия Александровича Ляпунова, который с 1820 занимал различные административные должности в Казанском университете. Его дети —
Мих
аил, Виктор, Наталья и Екатерина —
стали родоначальниками четырех ветвей, в каждой из которых встречаются имена с мировой известностью. Михаил Васильевич был директором обсерватории при Казанском университете; его сын —
знаменитый математик и механик, созд
атель теории устойчивости Александр Михайлович Ляпунов. Виктор Васильевич был видным медиком; среди его внуков —
А.Н.Крылов —
известный математик, механик и кораблестроитель, и Андрей Николаевич Ляпунов —
отец Алексея Андреевича...
Основные труды Ляпунова
относятся к теории множеств, теоретическим вопросам программирования, математической лингвистике, математической биологии. Когда академик Мстислав Всеволодович Келдыш (1911 -
1978) организовал в 1953 в составе Математического института АН СССР Отделение п
рикладной математики (ныне Институт прикладной математики им. М.В.Келдыша РАН), он предложил Ляпунову возглавить в нём работы по программированию. С 1961 Алексей Андреевич работал в Институте математики Сибирского отделения АН СССР, где фактически создал о
тделение кибернетики. В Новосибирске он также основал кафедру теоретической кибернетики Новосибирского университета и лабораторию кибернетики Института гидродинамики СО АН СССР, которыми руководил до конца своей жизни. В 1964 Ляпунов был избран членом
-
корр
еспондентом АН СССР по Отделению математики. Награжден орденом Ленина, другими орденами СССР и медалями. В 1996 (посмертно) Алексею Андреевичу была присуждена медаль "Пионер компьютерной техники"
("Computer Pioneer"). На обратной стороне медали надпись: "К
омпьютерное общество признало Алексея Андреевича Ляпунова основателем советской кибернетики и программирования".
Уже в ранний период развития программирования были осознаны трудности в создании больших программ без предварительного составления подходящей блок
-
схемы в терминах достаточно крупных операций. В 1953 Алексей Андреевич предложил метод предварительного описания программ при помощи операторных схем, который ориентирован на четкое выделение основных типов операторов и на построение своеобразной алге
бры преобразований программ. Этот метод благодаря алгебраической записи оказался значительно более удобным, чем применявшийся ранее метод блок
-
схем. Он стал основным средством автоматизации программирования и был положен в основу развития идей советской шк
олы программирования. В дальнейшем эти идеи углублялись и развивались как советскими (Ю.И.Янов, А.П.Ершов), так и зарубежными учеными; на этом пути было достигнуто лучшее понимание того, как можно преобразовывать схемы программ эквивалентным образом и оцен
ивать получающуюся программу по виду ее логической схемы.
Большое место в кибернетическом наследии А.А.Ляпунова занимают исследования процессов управления в живых организмах. Применение в биологии методов математического моделирования и внедрение в биолог
ическую теорию и практику точных определений и доказательных рассуждений математического характера являлось не только заслугой, но и любимым детищем Ляпунова, фактического основоположника "математической биологии" в современной советской науке. Работы Ляпу
нова и его учеников в области математического моделирования биологических процессов весьма разнообразны по своей тематике. Основной и исходной областью является биогеоценология
-
исследование совокупностей 7
популяций, совместно существующих на общей террито
рии. Биогеоценозы являются естественными составными частями биосферы. Важность этих работ подтверждается тем фактом, что исследование ресурсов биосферы стало признанной международной проблемой...
На этом историческое введение можно считать законченным.
Переходим к первой части статьи "Фрагмент 4.
Часть
1.
Общие свойства алгоритмов
Двадцатый век в области науки и техники принес человечеству много крупнейших достижений: радио, телевидение, атомная энергия, космические полеты, электронные вычислительные
машины —
вот только главные вехи, известные каждому жителю Земли. Но есть и менее известные достижения, многострадальные –
генетика, кибернетика, вирусология и ... теория алгоритмов —
новая математическая дисциплина. Теория электронных вычислительных маши
н, теория и практика программирования не могут обойтись без нее. Сегодня математика и кибернетика предъявляют на нее свои права. Однако она, пожалуй, является самостоятельной наукой, которая готова служить всем наукам -
имеет свое лицо, свой предмет.
Назв
ание науки —
теория алгоритмов —
говорит о том, что ее предмет —
алгоритмы. Понятие алгоритма является и очень простым и очень сложным. Его простота —
в многочисленности всевозможных алгоритмов, с которыми люди постоянно имеют дело, в их обыденности. Но эт
и
же обстоятельства делают его туманным, расплывчатым, трудно поддающимся строгому научному определению. Пока договоримся, что всегда есть "исполнитель алгоритма"
—
некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система,
способная выполнить действия, предписываемые алгоритмом.
В упомянутой выше книге Криницкий Н.А. "Алгоритмы вокруг нас"
, Николай Андреевич пишет следующее. Разъясним понятие алгоритма в интуитивном смысле на ряде примеров (слова "в интуитивном смысле", ко
гда это не ведет к недоразумениям, будем опускать). К числу алгоритмов не относятся правила, что
-
либо запрещающие, например: "Вход посторонним запрещен", "Не курить", "Въезд запрещен" (изображается известным каждому водителю автомобиля знаком "кирпич"). Не
относятся к ним и правила, что
-
либо разрешающие, такие как "Разрешена стоянка автотранспорта", "Вход", "Место для курения". А вот —
"Уходя, гасите свет", "Идти слева, стоять справа" (на эскалаторе в метрополитене) —
это уже алгоритмы, хотя и очень примити
вные. Нужно отметить одну особенность алгоритма: дискретный характер процесса, определяемого самим алгоритмом. Правило "Во время движения по тротуару придерживайся правой стороны", хотя и является предписанием, но имеет непрерывный характер и потому не отн
осится к числу алгоритмов. От него резко отличается текст, который можно встретить на некоторых телефонах
-
автоматах:
"Приготовив двухкопеечную монету,
1.
опустите ее в приемное отверстие;
2.
снимите трубку и ожидайте звуковой сигнал;
8
3.
услышав длинный непрерывный
гудок, наберите требуемый номер и ожидайте ответный сигнал;
4.
услышав длинные гудки, ждите ответа абонента;
5.
услышав короткие частые гудки, повесьте трубку и получите монету обратно.
Подобные правила очень многочисленны и нередко имеют большое практическое значение, например, "компьютерный" алгоритм –
"PageRank"
(пэйдж
-
ранк) —
один из алгоритмов ссылочного ранжирования. Алгоритм применяется к коллекции документов, связанных гиперссылками (таких, как веб
-
страницы из всемирной паутины), и назначает каждому из них некоторое численное значение, измеряющее его "важность" или "авторитетность" среди остальных документов. Вообще говоря, алгоритм может применяться не только к веб
-
страницам, но и к любому набору объектов, связанных между собой взаимными ссылками, то ес
ть к любому графу. Большая заслуга в создании этого алгоритма принадлежит Сергею Брину и Ларри Пейджу, которые в 1996 тогда еще аспиранты Стэнфордского университета (университет им.Леланда Стэнфорда -
Stanford University, в сердце Кремниевой долины), начал
и работу над проектом "BackRub" —
поисковой системой по сети интернет. Через некоторое время "BackRub" была переименована в известный Google
. Развитие вычислительной техники и методов программирования способствовало уяснению того факта, что разработка алго
ритмов является необходимым этапом автоматизации. То, что сегодня записано в виде алгоритма, завтра будет выполняться роботами.
В настоящее время слово "алгоритм" вышло за пределы математики. Его стали применять в самых различных областях, понимая под ним точно сформулированное правило, назначение которого —
быть руководством для достижения необходимого результата.
Термин "Алгоритм"
происходит от algorithmi -
латинского написания имени аль
-
Хорезми, под которым в средневековой Европе знали величайшего матем
атика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783
-
850 гг. В своей книге "Об индийском счете" он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем ал
горитмом стали называть точное предписание (набор инструкций исполнителю), определяющее порядок действий исполнителя, обеспечивающее получение требуемого (желаемого) результата для исходных данных за конечное число действий. Первые попытки уточнения поняти
я алгоритма и его исследования осуществляли в первой половине XX века Алан Тьюринг, Эмиль Пост, Жак Эрбран, Курт Гедель, Андрей Марков, Алонзо Чёрч. Было разработано несколько определений понятия алгоритма, но впоследствии было выяснено, что все они опреде
ляют одно и то же понятие. В результате был получен "Сильный тезис Чёрча —
Тьюринга"
(тезис Чёрча —
Тьюринга —
Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим у
стройством.
Обратите внимание: в старой трактовке вместо слова "порядок" использовалось слово "последовательность"
, но по мере развития параллельности в работе компьютеров слово "последовательность" стали заменять более общим словом "порядок". Это связано
с тем, что выполнение каких
-
то инструкций алгоритма может быть зависимо от результатов работы других инструкций -
некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструк
ции, ставшие независимыми из
-
за 9
завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.
Мухаммед бен Муса
Алгоритм м
ожет быть предназначен для выполнения его человеком или автоматическим устройством. Но создание алгоритма, пусть даже самого простого, -
процесс творческий
, он доступен пока исключительно живым существам, а долгое время считалось, что только человеку. Реал
изацию уже имеющегося алгоритма можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно даже и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Примером формального исполнителя мо
жет служить стиральная машина
-
автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являютс
я различные автоматические устройства и компьютер в том числе. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершать исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.
Приведенное выше определение алгоритма нельзя считать строгим. Из него не вполне ясно, что такое "точное предписание" или "послед
овательность действий, обеспечивающая получение требуемого результата". Поэтому обычно формулируют несколько общих свойств алгоритмов
, позволяющих отличать алгоритмы от других инструкций (указаний).
Коротко о важных свойствах алгоритмов:
Дискретность
-
а
лгоритм должен представлять процесс решения задачи как выполнение простых (или ранее определенных) инструкций. Некоторые инструкции, предусмотренные алгоритмом, должны исполняется только после того, как закончилось исполнение инструкций, от которых они зав
исят.
Определенность
-
каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаем
ой задаче.
Результативность
-
алгоритм должен приводить к решению задачи за конечное число шагов.
Массовость
-
алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только 10
исходным
и данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Алгоритмы, в зависимости от предполагаемого исполнителя, обычно задают тремя наиболее употребляемыми способами:
1.
на естественном языке;
2.
на языке блок
-
схем;
3.
на алгоритмическом языке.
Для начинающих программировать, наиболее подходящим можно признать язык блок
-
схем. Блок
-
схемой называют наглядное графическое изображение алгоритма, когда отдельные его действия (шаги или этапы) изображ
аются при помощи различных геометрических фигур (блоков), а связи между этапами указываются при помощи стрелок, соединяющих эти фигуры. Перечень условных обозначений, наиболее часто используемых для представления алгоритмов в графической форме, приведен на
рисунке ниже. Перечень в основном соответствует ГОСТ 19.701
-
90
(ИСО 5807
-
85) "Единая система программной документации. Схемы алгоритмов программ, данных и систем. Условные обозначения и правила выполнения".
Рисунок у
словны
х
графически
х
обозначени
й привед
ен на следующем листе
.
Переходим ко второй части статьи "Фрагмент 4.
Часть 2. Распараллеливание алгоритмов
Уже более 40 лет "параллельное программирование" считается перспективным направлением. Мечта об использовании параллельных алгоритмов и распар
аллеливающих компиляторах появилась в начале семидесятых годов прошлого века, практически сразу после появления первого параллельного суперкомпьютера ILLIAC IV. Работы по созданию компьютера начались в 1967, к концу 1971 изготовлена система из 1 квадранта,
в 1974 она введена в эксплуатацию, доводка велась до 1975.
11
Обозначения у
словные
графические
12
Суперкомпьютер ILLIAC IV
Это был многопроцессорный
суперкомпьютер с SIMD
-
архитектурой
(single instruction, multiple data —
одиночный поток команд, мн
ожественный поток данных). SIMD
-
компьютеры состоят из одного командного процессора (управляющего модуля), называемого контроллером, и нескольких модулей обработки данных, называемых процессорными элементами.
Схема компьютера ILLIAC IV
приведена на следующе
м листе.
Проведение обработки информации, включающей методы преобразования информации в данные и принципы взаимодействия технических средств и программного обеспечения связаны с архитектурой вычислительной машины (Computer architecture). Иными словами, пр
облема связана с концептуальной структурой вычислительной машины. С этой точки зрения представляет интерес "таксономия Флинна"
(Flynn's taxonomy) —
общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. Она была пре
дложена в 1970
-
е годы Майклом Флинном. Всё разнообразие архитектур ЭВМ в этой таксономии Флинна сводится к четыр
е
м классам:
* ОКОД
—
Вычислительная система с одиночным потоком команд и одиночным потоком данных (SISD, Single Instruction stream over a Single
Data stream).
* ОКМД
—
Вычислительная система с одиночным потоком команд и множественным потоком данных (SIMD, Single Instruction, Multiple Data).
* МКОД
—
Вычислительная система со множественным потоком команд и одиночным потоком данных (MISD, Multiple I
nstruction Single Data).
* МКМД
—
Вычислительная система со множественным потоком команд и множественным потоком данных (MIMD, Multiple Instruction Multiple Data).
13
Схема компьютера ILLIAC IV
В области систем обработки информации следует придерживатьс
я стандарта,
устанавливающего термины и определения понятий:
http://www.allsnips.info/docs/20/20325/index.htm
ГОСТ 15971
-
90
Системы обработки информации. Термины и определения.
Information p
rocessing systems. Terms and definitions.
14
Параллельные вычисления
использовались много лет в высокопроизводительных вычислениях (
"числодробилки"
), но в последнее время к ним возрос интерес вследствие достижения существенного физического ограничения на р
ост тактовой частоты процессоров. Параллельные вычисления стали доминирующей парадигмой в архитектуре компьютеров, в основном в форме многоядерных процессоров. Но побудительными факторами распараллеливания алгоритмов, пожалуй, следует признать два принципи
ально различных случая:
"естественный"
–
параллелизм заложен в самой природе задачи;
"искусственный"
–
параллелизм "создается" для достижения некоторой цели.
При рассмотрении стилей программирования выясняется, что зачастую линейный порядок исполнения опе
раторов программы навязывается ей извне и служит лишь подпоркой, необходимой для реализации в конкретной системе. Хорошим примером "естественного параллелизма алгоритмов" можно считать моделирование процессов методом Монте
-
Карло, базирующегося на проведени
и большого числа статистических испытаний. Естественно, с увеличением числа испытаний время работы программы линейно растет. Совершенно очевидной была идея произвести распараллеливание программы по испытаниям. См. например программу №4:
вычисление методом Монте
-
Карло (бросание точки в четверть круга случайным образом), приведенную во Фрагменте 2 "Все еще впереди".
Хорошим примером "искусственного параллелизма алгоритма" можно считать "умножение матриц" -
это случай, на котором достаточно широкие массы прог
раммистов и заказчиков вычислительных программ осознали потенциальную выгодность распараллеливания. Если разбить матрицу произведения k*m x l*n на подматрицы размера m x n, то для вычисления каждой такой подматрицы достаточно иметь m строк первого сомножит
еля и n столбцов второго. Разделив вычисления по независимым процессорам, мы можем ценой некоторого дублирования исходных данных значительно быстрее получить результат. Аналогично распараллеливается задача решения системы линейных уравнений.
Кстати, пионе
ром в параллельной обработке потоков данных был академик Александр Андреевич Самарский
(1919 —
2008), который с 1948 совместно с академиком А.Н.Тихоновым разрабатывал численные методы и провел первые в СССР прямые расчеты мощности взрыва атомной, а позже —
водородной бомбы, хорошо совпавшие с испытаниями. В этих работах были заложены основы математического моделирования и созданы важнейшие принципы конструирования и обоснования разностных схем и параллельных вычислений. Рассказывают, что в начале 50
-
х годов
решая задачу и лишивших доступа к ЭВМ, Самарский посадил несколько десятков барышень с арифмометрами за столы. Барышни передавали данные друг другу просто на словах и откладывали необходимые цифры на арифмометрах. Таким образом, в частности, была рассчита
на эволюция взрывной волны. Работы было много, барышни уставали, а Александр Андреевич ходил между ними и подбадривал.
Понятия вычислительного процесса и используемого ресурса являются основными при рассмотрении операционных систем (ОС). Здесь принято раз
личать два объекта:
Процесс (
Process
-
исполняемая задача), при выполнении ОС создает полноценную "виртуальную машину", выделяя процессу собственное адресное пространство и другие необходимые ресурсы. В общем случае процессы никак 15
не связаны между собой и
могут принадлежать даже различным пользователям. ОС считает процессы несвязанными и независимыми при этом ОС берет на себя роль арбитра в конкуренции по поводу ресурсов.
Тред (
Thread
-
нить исполнения), при выполнении ОС не создает полноценную "виртуальн
ую машину", а лишь выделяет процессорный ресурс. В однопроцессорной системе треды разделяют между собой процессорное время также, как это делают обычные процессы. В мультипроцессорной системе треды могут выполняться одновременно, если не встречают конкурен
ции из
-
за обращения к другим ресурсам.
Любая программа имеет как минимум один поток. В нем все происходит последовательно в соответствии с логикой алгоритма. Его можно назвать основным потоком. Но очень часто при разработке ресурсоемких программ, програм
мисты делят выполнение программы на несколько почти автономных частей
, выполняющихся одновременно, что дает существенный прирост производительности.
Компилятор FreeBASIC
имеет "встроенные" функции для организации многопоточной организации вычислений:
-
Функция
ThreadCall
threadid = Threadcall subname([paramlist])
Starts a procedure with parameters in a separate thread of execution.
-
Функция
ThreadCreate
result = ThreadCreate(proc [, [ param ] [, stack_size ] ])
Starts a procedure in a separate thread of execution.
Функции пользователя запускаются как нить и выполняются параллельно с основной частью программы. Это достигается операционной системой путем назначения его на другой процессор, если он существует, или использованием время ожидания в основной программе.
-
Функция
ThreadWait
Waits until a threaded procedure has finished.
ThreadWait(id)
В качестве п
араметр
а выступает идентификатор, возвращенный функцией ThreadCreate.
Ниже приведен текст программы, с помощью которой можно сравнить время вычисле
ний при последовательном исполнении некоторых сопрограмм Sub Coroutine1 и Sub Coroutine2 и их параллельном исполнении, правда, в одноядерном
состоянии компьютера.
16
' P R O G R A M "Example"
' 10.10.201
2
'
-------------------------------------------------------------
' Выполнение двух сопрограмм, вариант №1 и №2
'
-------------------------------------------------------------
'
#Lang "fb" ' режим FreeBASIC
-
совместимости (умолчание)
'
Sub Corouti
ne1(param1 As Any Ptr)
Dim I As Integer
I = 0
Do
View Print 1 To 2
Print "Coroutine1, I = "; I;
Sleep(120)
I = I + 1
Loop While I < 100
View Print 3 To 4
Print "Thread Coroutine1 ended";
End Sub
'
Sub Coroutine2(param2 As Any Ptr)
Dim I As Inte
ger
I = 0
Do
View Print 5 To 6
Print "Coroutine2, I = "; I;
Sleep(60)
I = I + 1
Loop While I < 100
View Print 7 To 8
Print "Thread Coroutine2 ended";
End Sub
'
' Главная программа запуска
ющая
сопрограммы
'
Dim As Double Start
Dim As Any Ptr Th
read1, Thread2
Start = Timer ' запомнить время старта
Cls
View Print 9 To 10
Print "Start!" ' сообщить о запуске
Thread1 = ThreadCreate(@Coroutine1()) ' запустить процесс 1
ThreadWait(Thread1) ' если вариант №1
Thread2 = ThreadCreate(@Coroutine2()) ' запустить процесс 2
ThreadWait(Thread1) ' если
вариант
№2
ThreadWait(Thread2)
View Print 11 To 12
Print "Done!"; Timer
-
Start ' время
выполнения
~18.28 ~12.21 с
Sleep
'
17
В програм
ме, для выбора конкретного варианта, необходимо "отключить" один их операторов ThreadWait(Thread1).
В строке Print
"
Done
!"
указано время ис
полнения программы для двух указанных вариантов.
Очевидно, что в случаях, когда параллельно протекающим процессам не
обходимо взаимодействовать, требуется их "синхронизация".
Для её организации используются средства межпроцессного взаимодействия. Средств синхронизации существует несколько, самые важные из них –
это
:
взаимоисключение (
mutex
),
критическая секция (
critical section
),
событие (
event
)
семафор (
semaphore
).
Каждый из этих средств
реализует свой способ синхронизации.
Рассмотренный выше комплекс проблем буквально неисчерпаем
, а ресурс общения –
ограничен!
На этом позвольте закруглиться.
До новых встреч!
Пиши
те: eugene_r@mail.ru
Документ
Категория
Информатика
Просмотров
383
Размер файла
767 Кб
Теги
алгоритм программирование freebasic
1/--страниц
Пожаловаться на содержимое документа