Файл: Тема Построение математических моделей для решения практических задач. Архитектура современных компьютеров. Многопроцессорные системы.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.01.2024
Просмотров: 803
Скачиваний: 8
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
одним ядром. В ответе укажите сумму этого числа и времени, прошедшего с момента начала вычислений до их завершения.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1; 2 |
| 4 | 7 | 3 |
| 5 | 5 | 0 |
Рассмотрим пример выше в случае, если устройство имеет 2 вычислительных ядра: ядро I и ядро II. Независимые процессы 1, 2 и 5 готовы к выполнению, но запустятся только процессы 5 (пусть на ядре I) и 1 (на ядре II) как имеющие большее время выполнения. При этом процесс 1 завершится через 4 мс после старта, и на освободившемся ядре II начнётся выполнение процесса 2. Оно продлится 3 мс и завершится через 4 + 3 = 7 мс после старта. Процесс 5 завершится через 5 мс после старта, но процесс 3 может быть запущен только после завершения процессов 1 и 2, поэтому ядро I останется свободным. Заметим, что процессы 3 и 4 выполняются последовательно и могут быть выполнены на одном и том же ядре. К моменту завершения процесса на ядре I был выполнен 1 процесс (ID 5), а на ядре II — 2 процесса (ID 1 и 2). Тогда максимальное число процессов, выполненных на одном ядре, будет достигнуто, если процессы 3 и 4 запустить на ядре II, и составит 4. Процесс 3 продлится 1 мс и закончит выполнение через 7 + 1 = 8 мс после старта. Процесс 4 продлится 7 мс и завершится через 8 + 7 = 15 мс после старта. Таким образом, вычисления завершились через 15 мс. Ответ будем сумма 15 и 4 (наибольшее число процессов на одном ядре), т.е. 19.
-
(А. Куканова) В файле 22-46.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Вычислительное устройство имеет 3 вычислительных ядра. Каждый из параллельных процессов выполняется на отдельном ядре. Освободившееся ядро сразу же занимается готовым к выполнению процессом (если они есть), причём в первую очередь запускаются процессы с наибольшим временем выполнения (если таких больше, чем свободных ядер, приоритет имеют процессы с меньшими ID). Определите наибольшее возможное число процессов, выполненных
одним ядром. В ответе укажите сумму этого числа и времени, прошедшего с момента начала вычислений до их завершения.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1; 2 |
| 4 | 7 | 3 |
| 5 | 5 | 0 |
Рассмотрим пример выше в случае, если устройство имеет 2 вычислительных ядра: ядро I и ядро II. Независимые процессы 1, 2 и 5 готовы к выполнению, но запустятся только процессы 5 (пусть на ядре I) и 1 (на ядре II) как имеющие большее время выполнения. При этом процесс 1 завершится через 4 мс после старта, и на освободившемся ядре II начнётся выполнение процесса 2. Оно продлится 3 мс и завершится через 4 + 3 = 7 мс после старта. Процесс 5 завершится через 5 мс после старта, но процесс 3 может быть запущен только после завершения процессов 1 и 2, поэтому ядро I останется свободным. Заметим, что процессы 3 и 4 выполняются последовательно и могут быть выполнены на одном и том же ядре. К моменту завершения процесса на ядре I был выполнен 1 процесс (ID 5), а на ядре II — 2 процесса (ID 1 и 2). Тогда максимальное число процессов, выполненных на одном ядре, будет достигнуто, если процессы 3 и 4 запустить на ядре II, и составит 4. Процесс 3 продлится 1 мс и закончит выполнение через 7 + 1 = 8 мс после старта. Процесс 4 продлится 7 мс и завершится через 8 + 7 = 15 мс после старта. Таким образом, вычисления завершились через 15 мс. Ответ будем сумма 15 и 4 (наибольшее число процессов на одном ядре), т.е. 19.
-
(А. Кабанов) В файле 22-55.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Определите, какое наибольшее количество процессов может быть завершено за первые 60 мс с момента запуска первого процесса.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1; 2 |
| 4 | 7 | 3 |
Пусть нас интересуют процессы, которые завершились в первые 6 мс. В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 – через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс и закончится через 5 + 7 = 12 мс. За первые 6 мс успеют завершиться процессы 1, 2, 3. Ответ для этого примера: 3.
-
(А. Кабанов) В файле 22-56.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Определите, какое наибольшее количество процессов может быть завершено за первые 40 мс с момента запуска первого процесса.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1; 2 |
| 4 | 7 | 3 |
Пусть нас интересуют процессы, которые завершились в первые 6 мс. В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 – через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс и закончится через 5 + 7 = 12 мс. За первые 6 мс успеют завершиться процессы 1, 2, 3. Ответ для этого примера: 3.
-
(Е. Джобс) В файле 22-57.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Определите максимально возможное целочисленное неизвестное время выполнения процесса t, если известно, что при его уменьшении минимально возможное время выполнения всей совокупности процессов не меняется.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | t | 1; 2 |
| 4 | 7 | 3 |
Пусть выполнение данной совокупности процессов закончилось за 15 мс. В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 – через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится t мс и закончится через 4 + t мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 4 + t мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 4 + t + 7 = 15 мс. Следовательно, t = 15 – 4 – 7 = 4 мс. Ответ для этого примера: 4.
-
(Е. Джобс) В файле 22-58.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение сразу же после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Для одного из процесса неизвестно, после какого процесса х он должен начать работать. Известно, что минимальное время выполнения всех процессов равно 17 мс. Найдите номер процесса х.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 6 | x |
| 4 | 7 | 3 |
Пусть минимальное время выполнения данной совокупности процессов равно 10 мс. В данном случае минимальное время окончания процесса 1 – 4 мс от начала запуска процессов, процесса 2 – 3 мс, процесса 4 – 6 мс (3 мс + 3 мс), следовательно, третий процесс может завершиться за 10 мс. Так как время его выполнения 6 мс, то он