Обработка данныхю. Ответы на билеты

Назначение процесса обработки данных Процесс обработки данных в ИТ управляет решением с помощью ЭВМ вычислительных задач, отображающих функциональные задачи объекта управления, при помощи соответствующих моделей обработки данных, алгоритмов обработки данных и машинных программ
Концептуальный уровень - процедуры процесса обработки данных. Логический уровень - модели и методы формализующие процедуры обработки данных в ЭВМ. Физический уровень это аппаратная реализация. Нарисуйте общую схему взаимодействия процедур обработки данных и объясните состав и назначение процедур процесса обработки данных Одной из важнейших процедур информационного процесса обработки данных является организация вычислительного процесса, т.е. обслуживаниепоступающих на обработку заданий (очередей) и планирование (оптимизация последовательности) их обработки. На программно-аппаратном уровне эти функции выполняют специальные управляющие программы, являющиеся составной частью операционных систем, т. е. систем, организующих выполнение компьютером операций обработки данных. Процедура преобразования данных состоит в том, что ЭВМ выполняет типовые операции над структурами и значениями данных (сортировка, выборка, арифметические и логические действия, создание и изменение структур и элементов данных и т.п.) в количестве и последовательности, заданных алгоритмом решения вычисли­тельной задачи, который на физическом уровне реализуется последовательным набором машинных команд (машинной программой). На логическом уровне алгоритм преобразования данных выглядит как программа, составленная на формализованном человеко-машинном языке — алгоритмическом языке программирования. Отображение информации выполняется на экране дисплея (или на бумаге принтера, графопостроителя) в виде графических объектов. На логическом уровне процедура отображения использует законы аналитической геометрии. Основой математических моделей отображения являются аффинные преобразования и сплайн-функции Информационный процесс обработки данных на физическом уровне представляется аппаратно-программным комплексом, включающим ЭВМ и программное обеспечение, реализующее модели организации вычислительного процесса, преобразования и отображения данных. Поясните работу ЭВМ в основных режимах обработки данных пакетном, разделения времени, реального времени Различают 3 основных режима обработки данных на ЭВМ: Пакетный режим обработки задач (очередь заданий -пакетов, которые выполняются последовательно. Пакеты выбираются с диска, с другого машинного носителя, из канала связи. Пропускная способность ЭВМ максимальна.) Режим разделения времени ( каждое задание получает квант или несколько квантов времени, все задания находятся в памяти ЭВМ, используется страничная организация памяти, некоторые виртуальные страницы находятся на диске, возможен диалоговый режим ) Режим реального времени (физическик,технологические процессы – реакция системы должна быть мгновенна. Потеря информации из-за перегрузки ЭВМ – губительна) Как организуется планирование обработки вычислительных задач в вычислительной системе? При решении вычислительной задачи ЭВМ использует свои ресурсы в объеме и последовательности, определяемых алгоритмом решения. К ресурсам ЭВМ относятся объем оперативной и внешней памяти, время работы процессора, время обращения к внешним устройствам (внешняя память, устройства отображения). Естественно, что эти ресурсы ограничены. Поэтому и требуется найти наилучшую последовательность решения поступивших на обработку вычислительных задач. Процесс определения последовательности решения задач во времени называется планирование. При планировании необходимо знать, какие ресурсы и в каком количестве требует каждая из поступивших задач. Ана­лиз потребности задачи в ресурсах производится на основе ее программы решения. После анализа поступивших программ решения задач становится ясно, какая задача каких ресурсов требует и в каком объеме. Критерии, используемые при планировании, зависят от степени определенности алгоритмов решаемых задач. · порядок использования устройств ЭВМ при решении задач строго задан их алгоритмами, а порядок использования устройств ВС в задачах заранее не известен. (Критерий- минимизация суммарного времени решения вычислительных задач) · порядок использования устройств ЭВМ при решении задач не известен, а порядок использования устройств ВС в задачах строго определен (Критерий- максимизация загрузки ВС) Реализация функций и алгоритмов планирования вычислительного процесса происходит с помощью управляющих программ операционной системы ВС. Программа планировщик определяет ресурсоемкость каждой поступившей на обработку задачи и располагает их в оптимальной последовательности. Подключение ресурсов в требуемых объемах к программам выполнения задач осуществляет по запросу планировщика управляющая программа супервизор, которая тоже входит в состав операционной системы. Опишите модель обслуживания задач в многомашинной вычислительной системе с очередью. Организация обслуживания вычислительных задач Система с дискретными состояниями и с непрерывным временем Цель планирования процесса обработки данных: наилучшие значения производительности, загруженности ресурсов, времени простоя , пропускной способности, времени ожидания в очереди заданий. На логическом уровне обслуживания вычислительной задачи создается модель задачи обслуживания Прямая задача обслуживания – задаются входные параметры вычислительной системы результат- показатель эффективности организации вычислительного процесса (ОВП) Оптимизационная задача обслуживания – задается показатель эффективности ОВП Результат – оптимизированные параметры вычислительного процесса Система с дискретными состояниями (в каждый момент времени система находится в одном состоянии и число состояний ограничено и может быть пронумеровано ) и с непрерывным временем (момент перехода из одного состояния в другое случаен и возможен в любой момент) Вычислительная система изменяет свои состояния под действием изменения очереди заданий. Для уменьшения времени пребывания задания в системе необходимо при заданной интенсивности потока заявок или увеличивать количество ЭВМ или уменьшать время обслуживания каждой ЭВМ Организация очереди, поддержание ее структуры возлагаются на диспетчера Д1, а передача заданий из очере­ди на обработку в вычислительные машины, поддержание дисциплины обслуживания в очереди (поддержка системы приоритетов) осуществляются диспетчером Д2 (см. рис). В вычислительной системе диспетчеры реализуются в виде управляю­щих программ, входящих в состав операционных систем ЭВМ.
Как организуется планирование обработки вычислительных задач в вычислительной системе? Появление заданий при технологическом процессе обработки данных является случайным, но при решении задачи по программе должны быть учтены и минимизированы связи решаемой задачи с другими функциональными задачами, оптимизирован процесс обработки по ресурсному и временному критериям. Поэтому составной частью процедуры организации вычислительного процесса является планирование последовательности решения задач по обработке данных.
Эффективность обслуживания вычислительных задач (их программ) зависит прежде всего от среднего времени обслуживания где интенсивность потока обслуживания В вычислительной системе (и в многомашинной, и в одномашинной особенно) требуется решать проблему минимизации времени обработки поступивших в систему заданий. Иногда эта проблема трансформируется в задачу максимизации загрузки устройств ЭВМ, являющихся носителями ресурсов. При решении вычислительной задачи ЭВМ использует свои ресурсы в объеме и последовательности, определяемых алгоритмом решения. К ресурсам ЭВМ относятся объем оперативной и внешней памяти, время работы процессора, время обращения к внешним устройствам (внешняя память, устройства отображения). Естественно, что эти ресурсы ограничены. Поэтому и требуется найти наилучшую последовательность решения поступивших на обработку вычислительных задач. Процесс определения последовательности решения задач во времени называется планирование. При планировании необходимо знать, какие ресурсы и в каком количестве требует каждая из поступивших задач. Анализ потребности задачи в ресурсах производится на основе ее программы решения. После анализа поступивших программ решения задач становится ясно, какая задача каких ресурсов требует и в каком объеме. Критерии, используемые при планировании, зависят от степени определенности алгоритмов решаемых задач. · порядок использования устройств ЭВМ при решении задач строго задан их алгоритмами, а порядок использования устройств ВС в задачах заранее не известен. (Критерий- минимизация суммарного времени решения вычислительных задач) · порядок использования устройств ЭВМ при решении задач не известен, а порядок использования устройств ВС в задачах строго определен (Критерий- максимизация загрузки ВС) Реализация функций и алгоритмов планирования вычислительного процесса происходит с помощью управляющих программ операционной системы ВС. Программа планировщик определяет ресурсоемкость каждой поступившей на обработку задачи и располагает их в оптимальной последовательности. Подключение ресурсов в требуемых объемах к программам выполнения задач осуществляет по запросу планировщика управляющая программа супервизор, которая тоже входит в состав операционной системы. Одной из важнейших процедур информационного процесса обработки данных является организация вычислительного процесса, т.е. обслуживаниепоступающих на обработку заданий (очередей) и планирование (оптимизация последовательности) их обработки. На программно-аппаратном уровне эти функции выполняют специальные управляющие программы, являющиеся составной частью операционных систем, т. е. систем, организующих выполнение компьютером операций обработки данных. Какие программы операционной системы ЭВМ реализуют процедуры организации вычислительного процесса? Реализация функций и алгоритмов планирования вычислительного процесса происходит с помощью управляющих программ операционной системы ВС. Программа планировщик определяет ресурсоемкость каждой поступившей на обработку задачи и располагает их в оптимальной последовательности. Подключение ресурсов в требуемых объемах к программам выполнения задач осуществляет по запросу планировщика управляющая программа супервизор, которая тоже входит в состав операционной системы. Одной из важнейших процедур информационного процесса обработки данных является организация вычислительного процесса, т.е. обслуживаниепоступающих на обработку заданий (очередей) и планирование (оптимизация последовательности) их обработки. На программно-аппаратном уровне эти функции выполняют специальные управляющие программы, являющиеся составной частью операционных систем, т. е. систем, организующих выполнение компьютером операций обработки данных. В чем состоит суть процедуры преобразования данных и как она реализуется в ЭВМ? К важнейшим процедурам технологического процесса обработки относится процедура преобразования данных. Она связана с процедурой ОВП, поскольку программа преобразования данных поступает в оперативную память ЭВМ, и начинает исполняться после предварительной обработки управляющими программами процедуры ОВП. (Одной из важнейших процедур информационного процесса обработки данных является организация вычислительного процесса, т.е. обслуживаниепоступающих на обработку заданий (очередей) и планирование (оптимизация последовательности) их обработки) Процедура преобразования данных состоит в том, что ЭВМ выполняет типовые операции над структурами и значениями данных (сортировка, выборка, арифметические и логические действия, создание и изменение структур и элементов данных и т.п.) в количестве и последовательности, заданных алгоритмом решения вычислительной задачи, который на физическом уровне реализуется последовательным набором машинных команд (машинной программой). На логическом уровне алгоритм преобразования данных выглядит как программа, составленная на формализованном человеко-машинном языке — алгоритмическом языке программирования. ЭВМ понимает только машинные команды, поэтому программы с алгоритмических языков с помощью программ-трансляторов переводятся в последовательность кодов машинных команд. Программа преобразования данных состоит из описания типов данных и их структур, которые будут применяться при обработке, и операторов, указывающих ЭВМ, какие типовые действия и в какой последовательности необходимо проделать над данными и их структурами. Управление процедурой преобразования данных осуществляется в первую очередь программой решения вычислительной задачи, и если решается автономная задача, то никакого дополнительного управления процедурой преобразования не требуется. Программа решения вычислительной задачи преобразует значения объявленных типов данных, и, следовательно, в процессе выполнения программы происходит постоянная циркуляция потоков значений данных из памяти ЭВМ и обратно. При выполнении программы к одним и тем же значениям данных могут обращаться различные процедуры и операции, сами операции обработки могут между собой комбинироваться различным образом, многократно повторяться и дублироваться.
Опишите модели преобразования данных. Если информационная технология организована для периодического решения комплекса взаимосвязанных функциональных задач управления, тогда необходимо оптимизировать процедуру преобразования данных: · по критерию минимизации времени обработки (в режиме реального времени)
· по критерию минимизации объемов затрачиваемых вычислительных ресурсов (в мультипрограммном режиме). Программа решения вычислительной задачи преобразует значения объявленных типов данных, и, следовательно, в процессе выполнения программы происходит постоянная циркуляция потоков значений данных из памяти ЭВМ и обратно. При выполнении программы к одним и тем же значениям данных могут обращаться различные процедуры и операции, сами операции обработки могут между собой комбинироваться различным образом, многократно повторяться и дублироваться. Задачей управления процедурой преобразованияданных является, · минимизация информационных потоков между памятью ЭВМ и операциями (процессором), · исключение дублирования операций в комплексах функциональных программ. Первая часть задачи может быть формализована, если структурировать программу на типы применяемых в ней операций, совокупности используемых в них данных (назовем эти совокупности информационными элементами) и связи между ними. Тогда модель этой части задачи преобразования данных может быть представлена в виде двудольного графа, состоящего из множества узлов-операций, соединенных дугами с множеством узлов информационных элементов (рис). Граф преобразования данных Этот граф можно сделать раскрашенным, т. е пометить раз­личным цветом дуги, относящиеся к разным информационным элементам. Тогда задача минимизации информационных пото­ков в графовой интерпретации будет состоять в разбиении рас­крашенного графа на подграфы (модули), при котором миними­зируется суммарное число дуг различного цвета, связывающих выделенные подграфы. Для удобства математического описания задачи управления процедурой преобразования данных и метода ее решения сведем граф, представленный на рис. , к табличной форме, располо­жив по строкам выполняемые операции, а по столбцам — эле­менты множества идентификаторов исходных, промежуточных и выходных данных, связанных с выполнением этих операций. На пересечении строки и столбца ставится 1, если операция и информационный элемент связаны. Другими словами, получим матрицу L: — если информационный элемент используется при выполнении операции A; — противном случае; При таком представлении задача состоит в разбиении множества операций преобразования данных матрицы L на непересекающиеся подмножества (модули), суммарное число информацион­ных связей между которыми минимально. При решении задачи должны быть учтены ограничения: на число выделяемых подмно­жеств (модулей); на число информационных элементов, входящих в один модуль; на число информационных связей между выделяе­мыми модулями; на совместимость операций в модулях. Данная задача может быть сведена к задаче линейного программирования и решена с использованием стандартных приклад­ных программ. Нарисуйте и объясните примеры графов алгоритмов и вычислительного графа программной системы. Алгоритм решения большой и сложной задачи, особенно ком­плекса задач, включает многократное использование типовых операций в различных комбинациях. Причем эти комбинации тоже могут многократно исполняться в соответствующих частях боль­шой программной системы. Поэтому второй частью задачи уп­равления процедурой преобразования данных являются выделе­ние в алгоритмах решения задач (или задачи) общих операцион­ных комбинаций, выделение их в общие модули и упорядочение таким образом общей схемы алгоритма обработки данных. Эта задача на логическом уровне может быть представлена как задача укрупнения графов алгоритмов. Граф алгоритма представляет собой древовидный граф, узла­ми которого являются операции над данными, а дугами — связи (отношения) между операциями в алгоритме. В корне графа рас­положена головная (начальная) операция а0, от которой после ее выполнения происходит переход к операции А1 или a2 , затем к А3,А 4, ., Ат Граф алгоритма Приведенный граф можно разметить, написав возле дуг чис­ло обращений rij от операции Аi, к операции aj (например, от А1 к A3) в процессе выполнения алгоритма. Для детерминирован­ных алгоритмов число обращений rij ≥1, для вероятностного ал­горитма число rij При анализе алгоритмов решения вычислительных задач можно выделить общие совокуп­ности операций (пересечения графов см рис ниже). Алгоритмы Р1 и p2 имеют три общие операции, составляющие подмножество операций, входящих одновременно и в множество операций ал­горитма Р1, и в множество операций алгоритма p2 (заштрихо­ванная часть рис.). Рис.Объединение графов алгоритмов Найдя такие пересечения алгоритмов, общие операции вмес­те с их отношениями выделяют в модули. Тогда совокупность алгоритмов может быть представлена в виде вычислительного графа процедуры преобразования данных, в которой определена последовательность выполнения модулей программной системы. Фрагмент вычислительного гра­фа программной системы, головным является вычислительный модуль М0. Ему подчинены модули, находящиеся на нижележа­щих уровнях. На самом нижнем уровне расположены модули, выполняющие элементарные типовые операции. Подобная организация алгоритмов преобразования данных позволяет на физическом уровне создать ясную и надежную сис­тему обработки, минимизирующую межоперационные связи. Изложенный подход реализуется методом структурного програм­мирования, применяемым при создании программных комплексов. Процедура преобразования данных на физическом уровне осуществляется с помощью аппаратных средств вычислительной системы (процессоры, оперативные и внешние запоминающие устройства), управление которыми производится машинными программами, реализующими совокупность алгоритмов решения вычислительных задач В чем состоит принцип параллельной обработки данных? Необходимость параллельной обработки данных возникает, когда требуется сократить время решения данной задачи, увеличить пропускную способность, улучшить использование системы.
Для распараллеливания необходимо соответствующим обра­зом организовать вычисления: · составление параллельных программ, т.е. отображение в явной форме параллельной обработки с помощью надлежащих конструкций языка, ориентированного на параллельные вычисления; · автоматическое обнаружение параллелизма.
Последовательная программа автоматически анализируется, в результате может быть выявлена явная или скрытая параллельная обработка. Скрытая параллельная обработка должна быть преобразована в явную. Граф выполнения большой программы Из рис. видно, что выполнение процесса Р5 не может на­чаться до завершения процессов p2 и рз и, в свою очередь, вы-полнение процессов p2 и p3 не может начаться до завершения процесса Р1 . В данном случае для выполнения программы достаточно трех процессоров. Ускорение обработки данных на многопроцессорной системе определяется отношением времени однопроцессорной обработ­ки Ts к времени многопроцессорной обработки Тт,. При автоматическом обнаружении параллельных вычислений определяются возможность яв­ной и скрытой параллельной обработки. Скрытая параллельная обработка требует некоторой процедуры преобразования последовательной программы, чтобы сделать возможным ее параллельное выпол­нение. При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализи­руются множества входных (считываемых) переменных R (Read) и выходных (записываемых) переменных W (Write) каждого про­цесса. Два процесса i, j (ij) могут выполняться параллельно при следующих условиях: Это означает, что входные данные одного процесса не долж­ны модифицироваться другим процессом и никакие два процесса не должны модифицировать общие переменные. Явная параллель­ная обработка может быть обнаружена среди процессов, удов­летворяющих этим условиям. Для использования скрытой парал­лельной обработки требуются преобразования программных конструкций: такие, как уменьшение высоты деревьев арифмети­ческих выражений, преобразование линейных рекуррентных со­отношений, замена операторов, преобразование блоков IF и DO в канонический вид и распределение циклов. Что такое конвейерная и векторная обработка данных? Конвейерная обработка улучшает использование аппаратных ресурсов для заданного набора процессов, каждый из которых применяет эти ресурсы заранее предусмотренным способом. Пример конвейерной организации сборочный транспортер на производстве, на котором изделие последовательно проходит все стадии вплоть до готового продукта. Преимущество этого способа состоит в том, что каждое изделие на своем пути использует одни и те же ресурсы, и как только некоторый ресурс освобождается данным изделием, он сразу же может быть использован следующим изделием, не ожидая, пока предыдущее изделие достигнет конца сборочной линии. Если транспортер несет аналогичные, но не тождественные изделия, то это последовательный конвейер; если же все изделия одинаковы, то это векторный конвейер. Последовательные конвейеры. На рис.представлена схема устройства обработки команд, в котором имеются четыре сту­пени: выборка команды из памяти, декодирование, выборка операнда, исполнение. 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 Ускорение обработки в данном устройстве измеряется отношением времени Ts, необходимого для последовательного выполнения L заданий (т.е. выполнения L циклов на одной обрабатывающей ступени), ко времени Тp выполнения той же обработки на конвейере. Обозначим через ti- время обработки на 1-й ступени, а через tj— соответствующее время для самой медленной ступени (рис). Тогда, если L заданий (команд) проходят через конвейер с n ступенями, эффективность конвейера определяется выражением Конвейеризация эффективна только тогда, когда загрузка конвейера близка к полной, а скорость подачи новых операндов соответствует максимальной производительности конвейера. Если происходит задержка операндов, то параллельно будет выполняться меньше операций и суммарная производительность снизится. Векторные конвейеры. В них создается множество функциональных элементов, каждый из которых выполняет определенную операцию с парой операндов, принадлежащих двум разным векторам. Эти пары подаются на .функциональное устройство, и функциональные преобразования со всеми элементами пар векторов проводятся одновременно. Для предварительной Подготовки преобразуемых векторов используются векторные регистры, на которых собираются подлежащие обработке векторы. Типичное использование векторного конвейера — это процесс, вырабатывающий по двум исходным векторам А и В ре­зультирующий вектор С для арифметической операции С ¬ А +В. В этом случае на конвейер поступает множество одинаковых команд. Для настройки конвейера на выполнение конкретной операции может потребоваться некоторое установочное время, однако затем операнды могут поступать на конвейер с максимальной скоростью, допускаемой возможностями памяти. При этом не возникает пауз ни в связи с выборкой новой команды, ни в связи с определением ветви вычислений при условном переходе. Главный принцип вычислений на векторной машине состоит в выполнении некоторой элементарной операции или комбинации из нескольких элементарных операций, которые должны повторно применяться к некоторому блоку данных. Таким операциям в исходной программе соответствуют небольшие компактные циклы. КОНЦЕПЦИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С УПРАВЛЕНИЕМ ПОТОКОМ ДАННЫХ Существуют трудности, связанные с автоматизацией параллельного программирования, необходимой для широкого круга задач матричных ВС. В связи с этим актуальными являются исследования новых путей построения высокопроизводительных вычислительных систем, к которым относятся вычислительные системы с управлением потоком данных, или потоковые ВС. В системах с управлением потоками данных предполагается наличие большого числа специализированных операционных блоков для определения видов операций (сложения, умножения и т.п., отдельных для разных типов данных). Данные снабжаются указателями типа данных (тегами), на основании которых, по мере готовности данных к обработке, они загружаются в соответствующие свободные операционные блоки. При достаточном количестве операционных блоков может быть достигнут высокий уровень распараллеливания вычислительного процесса. Во всех рассмотренных ранее машинах и вычислительных системах порядок выполнения операций над данными при решении задачи строго детерминирован, он однозначно определяется последовательностью команд программы.
Принципиальное отличие потоковых машин состоит в том, что команды выполняются здесь не в порядке их следования в тексте программы, а по мере готовности их операндов. Как только будут вычислены операнды команды, она может захватывать свободное операционное устройство и выполнять предписанную ей операцию. В этом случае последовательность, в которой выполняются команды, уже не является детерминированной.
Потоковая программа размещается в массиве ячеек команд (рис).
Схема работы процессора с управлением потоком данных Команда наряду с кодом операции содержит поля, куда заносятся готовые операнды, и поле, содержащее адреса команд, в которые должен быть направлен в качестве операнда результат операции. Кроме того, каждой команде поставлен в соответствие двухразрядный тег (располагаемый в управляющем устройстве), разряды которого устанавливаются в «1» при занесении в тело команды соответствующих операндов. В состоянии тега «11» (оба операнда готовы) инициируется запрос к операционному коммутатору (ОК) на передачу готовой команды в соответствующее коду операции операционное устройство (ОУ). Результат выполнения команды над ее непосредственно адресуемыми операндами направляется через командный коммутатор (КК) согласно указанным в команде адресам в ячейки команд и помещается в поля операндов. Далее указанная процедура циклически повторяется, причем управление этим процессом полностью децентрализовано и не нуждается в счетчике команд. Управление ресурсами вычислительных систем. Алгоритм SPT В системах обработки данных в качестве основного критерия эффективности используется среднее время обслуживания заявок. При оперативной обработке вычислительных задач невозможно проводить одновременно и их сортировку. Задачи с различной длительностью решения поступают на процессор в случайном порядке. В связи с этим невозможно использовать режим SPT (Shortest-Processing-Task-first), назначающий задачи на решение в порядке убывания времени их решения. В реальных системах оперативной обработки информация о времени решения задач, как правило, отсутствует. Чтобы воспользоваться принципами планирования на основе алгоритма SPT, в систему вводятся средства, которые выявляют короткие и длинные работы непосредственно в ходе вычислительного процесса. Управление ресурсами вычислительных систем, алгоритм RR(Round-Robin)? Алгоритм RR(Round-Robin - алгоритм циклического обслуживания). Заявки на выполнение работ поступают с интенсивностью λ в очередь О, откуда они выбираются и исполняются процессором CPU. Для обслуживания отдельной заявки отводится постоянный квант времени q, достаточный для выполнения нескольких тысяч операций. Если работа была выполнена за время q, она покидает систему. В противном случае она вновь поступает в конец очереди и ожидает предоставления ей очередного кванта процессорного времени. Управление ресурсами вычислительных систем, алгоритм Макнотона? Рассмотрим систему с n идентичными процессорами, с помощью которой необходимо решить L независимых задач; каждая задача решается одним процессором в течение времени ti , где i = 1 , ., L. Требуется найти алгоритм, который для каждого данного пакета (набора) задач строил бы расписание решения задач на процессорах системы, обеспечивающее минимально возможное время решения. При этом достигается максимально возможная производительность системы. Пример: в двухпроцессорной системе и при наборе задач с временем их решения 3; 3; 2; 2; 2 возможны различные варианты назначения задач на решение. a) работает один процессор b) работают два процессора c) алгоритм Макнотона Рис Варианты расписаний для двухпроцессорной системы Минимальное общее время решения задач достигается в варианте в), для которого время решения пакета задач совпадает с соответствующим оптимальным значением T = Tопт = Q и в данном случае равно величине Q = max {max ti, ()·∑ti}. Величина Q является нижней границей для оптимального значения Tопт. Длина любого расписания T ≥max ti — максимального из времен решения задач пакета, в то же время T ≥ (·∑ti) длины расписания в том случае, когда до момента завершения решения последней из задач пакета ни один процессор не простаивает, т.е. все процессоры имеют 100 %-ную загруженность. В общем случае даже при n =2 задача поиска оптимального значения T очень сложная задача, т.к. все известные алгоритмы ее решения имеют трудоемкость, экспоненциально зависящую от L. Однако, если допустить возможность прерывания решения задач пакета до завершения их обслуживания, то могут быть предложены алгоритмы, приводящие к расписанию оптимальной длины Tопт. При этом считается, что после прерывания решение задачи может быть возобновлено с точки прерывания на любом процессоре, не обязательно на том, на котором задача решалась первоначально. Число прерываний должно быть по возможности меньшим, так как с каждым актом прерывания связаны потери машинного времени на загрузку-выгрузку задач из оперативной памяти. Рассмотрим алгоритм Макнотона построения оптимального по длине расписания с не более чем n-1 прерываниями. Алгоритм Макнотона заключается в предварительном упорядочении задач по убыванию времени решения и назначении задач последовательно по порядку номеров одну за другой на процессоры системы справа налево от уровня Q. Примем: n= 2, L = 4, время решения задач: 5; 4; 3; 2. (N задачи 1;2;3;4) Тогда Q = max {5, ½ • (5 + 4 + 3 + 2)} = 7; расписание, в соответствии с алгоритмом Макнотона, имеет вид, таблицы. 2-й процессор 2
1 1-й процессор 4 3 2
В данном примере число прерываний=1 (прерывание в задаче N=2, со временем=4 ). Покажем, что n-1 (максимальное число прерываний для расписания, полученного в соответствии с алгоритмом Макнотона) является достижимой границей числа прерываний.
Для доказательства этого построим такой пример пакета задач, для которого алгоритм Макнотона дает расписание с числом прерываний n-1. Пусть: L = n + 1 и ti = n, i =1,…, n + 1. Тогда: Q = max {n ,(1/n)·(n + 1)n} = n + 1, а расписание, получаемое в соответствии с алгоритмом Макнотона, имеет вид:
Число прерываний в этом случае, как видно, равно (n –1), что и требовалось показать. Покажем, что любое оптимальное расписание для этого пакета задач также имеет не менее n -1 прерываний. Очевидно, что в любом оптимальном расписании ни один процессор не простаивает на интервале [0, n + 1]. Предположим, что сущес-твует некоторое оптимальное расписание с числом прерываний, меньшим n -1. Тогда по крайней мере два процессора ( для определенности возьмем Рk и Pu) обслуживают заявки без прерываний. Очевидно, эти процессоры обслуживают некоторые задачи Zik и Ziu в интервале [0, n] без прерываний, (если решение этих задач начинается позже момента времени t = 0, значит, до этого момента на этих процессорах решались некоторые другие задачи, решение которых прерывается в моменты начала решения задач Zik и Ziu). Найдутся моменты времени t, t', такие, что n ≤ t Так как мы пришли к противоречию, делаем вывод о том, что предположение о числе прерываний, меньшем n-1, в оптимальном расписании ложно. В чем заключается основное достоинство обработки пакетов независимых задач без прерывания? МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ ПРИ ОБРАБОТКЕ ПАКЕТОВ НЕЗАВИСИМЫХ ЗАДАЧ БЕЗ ПРЕРЫВАНИЙ Рассмотрим систему, содержащую n идентичных процессоров, на которой необходимо решить без прерываний набор из Lнезависимых задач с временами решения ti , где i = 1 , ., L. Получение расписания с минимальным временем решения и в этом случае является трудной задачей. Один из наиболее эффективных и нетрудоемких алгоритмов организации таких вычислений — алгоритм LPT (Longest-ProcessingTaskfirst — самая длинная задача решается первой), являющийся частным случаем алгоритма критического пути для независимых задач. Суть этого алгоритма - в назначении задач в порядке убывания времени решения на освобождающиеся процессоры. Сотрудником фирмы BellLaboratories, США, Грэхемом в 1967 г. был получен следующий результат: при использовании алгоритма LPT для распределения любого пакета П независимых задач без прерываний, в системе с n идентичными процессорами справедливо: где Т — время решения пакета П при распределении задач алгоритмом LPT; tо — длина оптимального расписания. Приведенная оценка является наилучшей. За счет чего увеличивается производительность мультипроцессорных систем по сравнению с однопроцессорными системами? Вычислительные системы, содержащие несколько процессоров, связанных между собой и с общим для них комплектом внешних устройств, называются мультипроцессорными системами (МПС). Производительность МПС увеличивается по сравнению с однопроцессорной системой за счет того, что мультипроцессорная организация создает возможность для одновременной обработки нескольких задач или параллельной обработки различных частей одной задачи. Как строятся мультипроцессорные системы с общей памятью? В ряде случаев требуется обеспечить непрерывность функционирования системы во времени. Это означает, что отказ в любом устройстве ВС, в том числе и в процессоре, не должен приводить к катастрофическим последствиям, т.е. система должна сохранять работоспособность и после отказа. В таком случае все устройства ВС должны быть по крайней мере задублированы и система должна содержать не менее двух процессоров, т.е. строиться как МПС. В МПС с общей памятью каждый из процессоров имеет доступ к любому модулю памяти, которые могут функционировать независимо друг от друга и в каждый момент времени обеспечивать одновременные обращения в целях записи или чтения слов информации, число которых определяется числом модулей. Конфликтные ситуации (обращение к одному и тому же модулю памяти) разрешаются коммутатором, начинающим обслуживать первым устройство с наибольшим приоритетом, например процессор с наименьшим номером. Каждый из процессоров может инициировать работу любого канала ввода-вывода. Структура МПС с общей памятью наиболее универсальна: любая информация, хранимая в памяти системы, в равной степени доступна любому процессору и каналу ввода-вывода. Отрицательное свойство МПС с общей памятью — большие затраты оборудования в коммутаторах (эти затраты пропорциональны произведению числа устройств, подключенных к памяти, и числа модулей памяти). Как строятся мультипроцессорные системы с индивидуальной памятью? В МПС с индивидуальной памятью каждый из процессоров обращается в основном к своему модулю памяти. Для обмена данными между подсистемами «процессор — модуль памяти» в процессорах предусмотрены блоки обмена, обеспечивающие передачу сегментов информации между общей памятью и модулем памяти. При этом блок обмена может работать как селекторный канал: операция обмена инициируется процессором, и передача данных выполняется с параллельной работой последнего. Принцип индивидуальной памяти позволяет исключить коммутаторы в интенсивно используемом канале «процессор — модуль памяти», вследствие чего увеличивается номинальное быстродействие процессоров и уменьшаются затраты оборудования по сравнению с системами с общей памятью. Отрицательным последствием разделения памяти между процессорами является потеря ресурсов быстродействия в процессе обмена информацией между модулями памяти и общей памятью системы. Потери возникают, во-первых, из-за возможных приостановок работы процессоров для ожидания моментов окончания обмена данными с общей памятью и, во-вторых, из-за дополнительной загрузки модулей памяти операциями обмена. . Какие недостатки имеет структура МПС с общей памятью перед МПС с индивидуальной памятью? Если, работа каждого процессора МПС связана с использованием в основном ограниченного подмножества данных и обращение к остальным данным происходит сравнительно редко, то индивидуализация памяти приводит к экономии оборудования и обеспечивает высокое номинальное быстродействие процессоров в системе.
Если каждый из процессоров почти равновероятно обращается к любому сегменту данных, МПС должна строиться по схеме с общей памятью, исключающей необходимость в обмене информацией между модулями памяти Для чего служит процедура отображения данных, и какие операции ее реализуют?
Процедура отображения данных — одна из важнейших в информационной технологии. Без возможности восприятия результата обработки информации человеческими органами чувств этот результат оставался бы вещью в себе (ведь мы не ощущаем машинное представление информации). Наиболее активно из человеческих органов — зрение, поэтому процедуры отображения в информационных технологиях, особенно организационно-экономических, преследуют цель как можно лучше представить информацию для визуального наблюдения. Конечно, в мультимедийных системах сейчас используется и аудио-, и видео-, и даже тактильное отображение данных, но при управлении предприятием более важным является отобра­жение данных в текстовой или в графической форме. Основные устройства, воспроизводящие текст или графические фигуры, — это дисплеи и принтеры, на использование которых (особенно первых) и направлены операции и процедуры отображения. Для того чтобы получить на экране дисплея (или на бумаге с помощью принтера) изображение, отображающее выводимую из компьютера информацию, данные (т.е. машинное представление этой информации) должны быть соответствующим образом преобразованы, затем адаптированы (согласованы) с параметрами дисплея и, наконец, воспроизведены. Все эти операции должны выполняться в строгом соответствии с заданной формой воспроизведения и возможностями воспроизводящего устройства. Согласование операций процедуры отображения производится с помощью управляющей процедуры ОВП (рис. ). В современных ИТ при воспроизведении информации предпочтение отдано не текстовым режимам , а графическим режимам работы дисплеев как наиболее универсальным Графический режим позволяет выводить на экран дисплея любую графику (ведь буквы и цифры тоже графические объекты), причем с возможностью изменения масштаба, проекции, цвета и т.д. Развитие информационных технологий ввода и вывода информации идет по пути создания объектно-ориентированных систем, в которых настройка систем, программирование функциональных задач, ввод и вывод информации осуществляются с помощью графических объектов, отображаемых на экране дисплея (примером могут служить широко распространенный графический интерфейс Windows, объектно-ориентированные языки Delphi, Java и т.д.). Что служит теоретической базой для создания моделей компьютерной графики? Отображение информации на экране дисплея (или на бумаге принтера, графопостроителя) в виде графических объектов (графиков, геометрических фигур, изображений и т. д.) носит название компьютерной (машинной) графики, начало которой было положено в 1951 г. инженером Массачусетского технологического института Дж. У. Форрестом. На логическом уровне процедура отображения использует законы аналитической геометрии, разработанной французским философом и математиком Р. Декартом в XVII в., согласно которой положение любой точки на плоскости (а экран дисплея — плоскость) задается парой чисел — координатами. Пользуясь декартовой системой координат, любое плоское изображение можно свести к списку координат составляющих его точек. И наоборот, заданные оси координат, масштаб и список координат легко превратить в изображение. Геометрические понятия, формулы и факты, относящиеся прежде всего к плоскому и трехмерному изображениям, играют в задачах компьютерной графики особую роль. Основой математических моделей компьютерной графики являются аффинные преобразования и сплайн-функции. Какие вы знаете преобразования на плоскости? В компьютерной графике все, что относится к двумерному случаю, принято обозначать символом 2D (2-dimension). Допустим, на плоскости введена прямолинейная координатная система. Тогда каждой точке М ставится в соответствие упорядоченная пара чисел (х, у) ее координат . Точка в прямоугольной системе координат Вводя на плоскости еще одну прямолинейную систему координат, мы ставим в соответствие той же точке М другую пару чисел — (x*, у*). Переход от одной прямолинейной координатной системы на плоскости к другой описывается следующими соотношениями: х* = αх + βy + λ; у* = γx + δу + μ, где α, β, γ,λ, μ — произвольные числа, связанные неравенством В аффинных (от лат. affinis — родственный) преобразованиях плоскости особую роль играют несколько важных частных случаев, имеющих хорошо прослеживаемые геометрические характеристики. Аффинная геометрия — раздел геометрии, в котором изучаются свойства фигур на плоскости (или в пространстве), сохраняющиеся при любых аффинных преобразованиях плоскости (или пространства), т.е. инвариантные относительно таких преобразований. При исследовании геометрического смысла числовых коэффициентов в формулах, помеченных символом «*», для этих случаев удобно считать, что заданная система координат является прямоугольной декартовой. Рассмотрим простейшие аффинные преобразования. А. Поворот (вокруг начальной точки на угол (φ) описывается формулами: х* = xcosφ - ysinφ, у* = xsinφ + ycosφ. Рис. Поворот точки на угол φ Б. Растяжение (сжатие) вдоль координатных осей можно задать так: х* = αх, у* = δу, α. > 0, δ > 0. Растяжение вдоль осей В. Отражение (относительно оси абсцисс) задается при помощи формул: х *= х; у * = - у. Отражение относительно оси абсцисс Г. Перенос. вектор переноса ММ* имеет координаты λ и μ. Перенос обеспечивают соотношения: х* = х + λ.; у* = у + μ. Перенос точки Выбор этих четырех частных случаев определяется следующими обстоятельствами. · Каждое из приведенных выше преобразований имеет простой и наглядный геометрический смысл (геометрическим смыслом наделены и постоянные числа, входящие в приведенные формулы). · Как доказывается в курсе аналитической геометрии, любое преобразование вида (*) всегда можно представить как последовательное использование (суперпозицию) простейших преобразований вида А, Б, В и Г (или части этих преобразований). Т.е. любое отображение вида (*) можно описать при помощи отображений, задаваемых формулами для случаев А, Б, В и Г.
Для эффективного использования этих формул в задачах компьютерной графики более удобной является их матричная запись. Матрицы, соответствующие случаям А, Б и В, строятся легко и имеют следующий вид: Однако для решения задач компьютерной графики весьма желательно охватить матричным подходом все четыре простейших преобразования (в том числе и перенос), а значит, и общее аффинное преобразование. Этого можно достичь, например, так: перейти к описанию произвольной точки на плоскости, не упорядоченной парой чисел, как это было сделано выше, а упорядоченной тройкой чисел.
Что такое однородные координаты точки, и при решении каких задач они применяются? Пусть М — произвольная точка на плоскости с координатами х и у, вычисленными относительно заданной прямолинейной координатной системы. Однородными координатами этой точки называется любая тройка одновременно не равных нулю чисел X1, X2, X3, связанных с заданными числами х и у следующими соотношениями: При решении задач компьютерной графики однородные координаты обычно вводятся так: произвольной точке М (х, у) на плоскости ставится в соответствие точка М*(х, у, 1) в пространстве. Рис. Преобразование координат точки на плоскости в однородные координаты Заметим, что произвольная точка на прямой, соединяющей начало координат, точку О(0, 0, 0) с точкой М*(х, у, 1), может быть задана тройкой чисел вида (hх, hу, h). Будем считать, что h¹0. Вектор с координатами hx, hy, h является направляющим вектором прямой, соединяющей точки О(0, 0, 0) и М*(х, у, 1). Эта прямая пересекает плоскость z = 1 в точке (х, у, 1), которая однозначно определяет точку (х, у) координатной плоскости хоу. Между произвольной точкой с координатами (х, у) и множеством троек чисел вида (hх, hу, h), h¹ 0, устанавливается (вза­имно однозначное) соответствие, позволяющее считать числа hх, hy, h новыми координатами этой точки. В проективной геометрии для однородных координат принято следующее обозначение: х : у : 1 или более общо: X1 : Х2 : X3 (напомним, что здесь непременно требуется, чтобы числа X1 , Х2 , X3 одновременно в нуль не обращались). Применение однородных координат оказывается удобным уже при решении простейших задач. Например, при изменении масштаба. Если устройство отображения работает только с целыми числами (или если необходимо работать только с целыми числами), то для произвольного значения h (например, h = 1) точку с однородными координатами (0,5; 0,1; 2,5) представить нельзя. Однако при разумном выборе h можно добиться того, чтобы координаты этой точки были целыми числами. В частности, при h = 10 - для рассматриваемого примера : (5; 1; 25). Другой случай. Чтобы результаты преобразования не приводили к арифметическому переполнению, для точки с координатами (80 000; 40 000; 1000) можно взять, например, h = 0,001. В результате получим: (80; 40; 1). Приведенные примеры показывают полезность использования однородных координат при проведении расчетов. Однако основной целью введения однородных координат в компьютерной графике является их несомненное удобство в применении к геометрическим преобразованиям. При помощи троек однородных координат и матриц третьего порядка можно описать любое аффинное преобразование плоскости. В самом деле, считая h = 1, сравним две записи: помеченную символом * и матричную: Нетрудно заметить, что после перемножения выражений, стоящих в правой части последнего соотношения, мы получим обе формулы (*) и тождество 1 = 1. Тем самым сравниваемые записи можно считать равносильными. Элементы произвольной матрицы аффинного преобразования не несут в себе явно выраженного геометрического смысла. Поэтому чтобы реализовать то или иное отображение, т.е. найти элементы соответствующей матрицы по заданному геометрическому описанию, необходимы специальные приемы. Обычно построение этой матрицы в соответствии со сложностью рассматриваемой задачи и с описанными выше частными случаями разбивают на несколько этапов. На каждом этапе ищется матрица, соответствующая тому или иному из выделенных выше случаев А, Б, В и Г, обладающих хорошо выраженными геометрическими свойствами. Выпишем соответствующие матрицы третьего порядка. А. Матрица вращения (rotation): Б. Матрица растяжения (сжатия) (dilatation): В. Матрица отражения (reflection): Г. Матрица переноса (translation): Эти матрицы - составляющие общей матрицы, преобразующей исходную матрицу А графического объекта в матрицу А* преобразованного объекта. Общая матрица преобразования при известных γ, λ, α, β и μ получается перемножением матриц простейших преобразований V = [R][D][M][T]. Основные свойства матричных преобразований при перехо­де к трехмерному (3D) преобразованию сохраняются, однако более сложной становится операция вращения, требующая задания оси вращения. Напомним, что однородное представление трехмерной точки имеет вид: (hx, hy, hz, h). Наличие точных математических моделей графических объектов позволяет относительно легко отображать их на экране монитора, а вычисленные матрицы преобразований дают возможность манипуляции этими объектами на экране как в статике, так и в динамике. Далеко не всегда удается получить точное функциональное описание объекта. Чаще всего оказывается возможным вычислить только ряд точек графической фигуры. И тогда возникает задача плавного соединения (а не прямыми) этих точек для восстановления на экране изображения воспроизводимой фигуры. Эта задача в компьютерной графике решается с помощью геометрических сплайнов. Определите понятие геометрического сплайна и приведите формальное описание сплайн-функций. Термин «сплайн» происходит от английского spline - гибкая полоска стали, при помощи которой чертежники проводили через заданные точки плавные кривые. В былые времена подобный способ построения плавных обводов различных тел, таких, как, например, корпус корабля, кузов автомобиля, а потом фюзеляж или крыло самолета, был довольно широко распространен в практике машиностроения. В результате форма тела задавалась при помощи набора очень точно изготовленных сечений — плазов. Появление компьютеров позволило перейти от этого метода к более эффективному способу задания поверхности обтекаемого тела. В основе сплайн-подхода к описанию поверхностей лежит использование относительно несложных формул сплайн-функций, позволяющих восстанавливать облик изделия с необходимой точностью.
Рассмотрим сплайны, в построении которых используются кубические (для одномерных сплайнов — сплайновых кривых) и бикубические (для двумерных сплайнов — сплайновых поверхностей) многочлены. В компьютерной графике подобные сплайны применяются наиболее часто. Достаточно типичной является следующая задача: по заданному массиву точек на плоскости (2D) или в пространстве (3D) построить кривую, проходящую либо через все эти точки (задача интерполяции), либо вблизи от этих точек (задача сглаживания).
Совершенно естественно возникают вопросы: в каком классе кривых искать решение поставленной задачи? как искать? А. Случай одной переменной. Обратимся для определенности к задаче интерполяции и начнем рассмотрение с обсуждения правил выбора класса кривых. Ясно, что допустимый класс кривых должен быть таким, чтобы решение задачи было единственным (это обстоятельство сильно помогает в преодолении многих трудностей поиска). Кроме того, желательно, чтобы построенная кривая изменялась плавно. На плоскости задан набор точек (Xi,Yi), i = 0,1, .,m таких, что х0 Благодаря тому, что точки заданного набора занумерованы в порядке возрастания Xi, можно искать кривую в классе графиков функции, а основные моменты сглаживания этого дис­кретного набора описывать, ограничившись многочленами. 1. Как известно из курса математического анализа, существует интерполяционный многочлен Лагранжа: график которого проходит через все заданные точки (Xi,Yi), i = 0,1, .,m Это обстоятельство и простота описания (заметим, что многочлен однозначно определяется набором своих коэффициентов; в данном случае их число совпадает с количеством точек в задан­ном наборе) являются несомненными достоинствами построенного интерполяционного многочлена. Однако полезно остановиться и на некоторых недостатках предложенного подхода. · Степень многочлена Лагранжа на единицу меньше числа заданных точек. Поэтому чем больше точек задано, тем выше степень такого многочлена. И хотя график интерполяционного члена Лагранжа всегда будет проходить через все точки массива, его уклонение (от ожидаемого) может оказаться довольно значительным. · Изменение одной точки (ситуация, довольно часто встре­чающаяся на практике) требует полного пересчета коэффициентов интерполяционного многочлена и к тому же может существен­но повлиять на вид задаваемой им кривой. 2. Приближенную кривую можно построить и совсем просто: если последовательно соединить точки заданного набора прямолинейными отрезками, то в результате получится ломаная. Приближенная ломаная При такой, кусочно-линейной, интерполяции требуется найти всего 2m чисел (каждый прямолинейный отрезок определяется ровно двумя коэффициентами), но, построенная таким образом аппроксимирующая кусочно-линейная функция не обладает нужной гладкостью. Рассмотрев эти две крайние ситуации, попробуем найти класс функций, которые сохранили бы перечисленные выше достоинства обоих подходов и были бы в известной степени свободны от их недостатков. Для этого будем использовать многочлены (как и в случае 1) и строить их последовательно, звено за звеном (как и в случае 2). В результате получится так называемый полиномиальный многозвенник. При подобном подходе важно правильно выбрать степени привлекаемых многочленов, а для плавного изменения ре­зультирующей кривой необходимо еще тщательно подобрать коэффициенты многочленов (из условия гладкого сопряжения соседних звеньев). То, что получится в результате описанных условий, называют сплайн-функциями или просто сплайнами. Для того чтобы понять, какое отношение имеют сплайн-функции к чертежным сплайнам, возьмем гибкую стальную линейку, поставим ее на ребро и, закрепив один из концов в заданной точке, поместим ее между опорами, которые располагаются в плоскости ОХУ в точках (Xi,Yi), i = 0,1, .,m таких, что х0 Рис Приближение сплайном Функция у = S(x), описывающая профиль линейки, обладает следующими свойствами: · с довольно большой точностью часть графика этой функции, заключенную между любыми двумя соседними опорами, можно считать многочленом третьей степени; · на всем промежутке [x0, Xm] функция у = S(x) дважды непрерывно дифференцируемая. Построенная функция S(x) относится к так называемым интерполяционным кубическим сплайнам. Достоинства предложенного способа : для решения линейных систем, возникающих в ходе построения сплайн-функций, существует много эффективных методов,эти системы достаточно просты; графики построенных сплайн-функций проходят через все заданные точки, полностью сохраняя первоначально заданную информацию. Недостатки - изменение лишь одной точки, при описанном подходе, заставляет пересчитывать заново, как правило, все коэффициенты. Во многих задачах исходный набор точек задается приближенно, и, значит, требование неукоснительного прохождения графика искомой функции через каждую точку этого набора оказывается излишним. В этом случае используются методы сглаживания, при которых можно отказаться от требования строго однозначного проектирования искомой кривой на координатную ось, а поверхности — на координатную плоскость Опишите два основных метода получения графического изображения на экране монитора На физическом уровне отображение производится в основном с помощью компьютерных дисплеев. При необходимости получения твердой копии используются принтеры и плоттеры. Основное использование дисплея в качестве оконечного устройства отображения связано с его высоким быстродействием, значительно превышающим скорость реакции человеческого глаза, что особенно важно в системах реального времени и при отображениях анимации и видеоизображении. Для получения графического изображения на экране дисплея используются два основных метода: векторный (функциональный) и растровый. Векторный метод предполагает вывод графического изображения с помощью электронного луча, последовательно «вычерчивающего» на экране дисплея линии и кривые в соответствии с математической моделью (функцией) этого объекта. «Вычерчивание» — это последовательное засвечивание пикселей экрана. Так как каждый пиксель имеет свою координату (пару чисел), то этот метод преобразует последовательность чисел (вектор) в светящиеся точки. Отсюда название метода. Для того чтобы изображение на экране было неподвижным для глаза человека, луч пробегает по определенным пикселям многократно (не менее 16 раз в секунду). Векторный метод — наиболее быстродействующий и применяется при выводе относительно несложных графических объектов (графики, чертежи, номограммы и т.п.) при научных и инженерных исследованиях. Еще одним очень важным достоинством метода являются минимальные для графических систем требования к ресурсам ЭВМ (памяти и производительности).
Растровый (экранный) метод привнесен в компьютерную графику из телевидения. При использовании этого метода электронный луч сканирует экран монитора (дисплея) слева направо, после каждого прохода опускаясь на одну строку пикселей, сотни раз в секунду (обычно 625 раз). После прохождения нижней строки луч возвращается к первой строке (обратный ход). Чтобы при обратном ходе на экране не прочерчивалась диагональная линия, луч на это время гасится. Такое сканирование экрана проводится 25 раз в секунду. Полностью просканированный экран называется кадром. Если интенсивность электронного луча постоянна, то на экране создается равномерный фон из одинаково светящихся пикселей. При выводе на экран графического объекта в соответствующих его модели точках интенсивность луча изменится, в результате чего «прорисовывается» сам графический объект. В цветных дисплеях можно задавать цвета как фона, так и изображения. Современные графические адаптеры дисплеев позволяют в принципе создавать бесчисленное множество цветов.
Растровый метод дает возможность отображать на экране дисплеев практически любое изображение, как статическое (неподвижное), так и динамическое (движущееся). Другими словами, метод универсален, но, как и все универсальное, требует больших затрат ресурсов ЭВМ. Поэтому если основной функцией вычислительной системы является работа с изображениями (системы автоматизации проектирования, системы создания и обработки изображений, анимация, создание киноэффектов и т.д.), то в этом случае разрабатываются специальные комплексы, называемые графическими станциями, в которых все ресурсы ЭВМ направлены на обработку, хранение и отображение графических данных. На каких аппаратно-программных средствах реализуется информационный процесс обработки данных? Информационный процесс обработки данных на физическом уровне представляется аппаратно-программным комплексом, включающим ЭВМ и программное обеспечение, реализующее модели организации вычислительного процесса, преобразования и отображения данных. В зависимости от сложности и функций информационной технологии аппаратно-программный комплекс обработки данных строится на базе или одного персонального компьютера, или специализированной рабочей станции, или на мейнфрейме, или на суперЭВМ, или на многомашинной вычислительной системе.