Лабораторная работа №1
Выполнил: студент
группы ВПР32
Благодарный А.В.
Проверил:
Кобак В.Г.
Ростов-на-Дону
Введение
Предметом области исследования расписаний является круг задач проектирования и организационного управления в различных системах, в которых требуется найти наилучшее (оптимальное) значение выбранных критериев их функционирования с учетом имеющихся ограничений.
Программирование для многопроцессорных машинных систем связано с распараллеливанием и синхронизацией вычислений и организацией выполнения параллельных вычислительных процессов. Это выдвигает целый ряд сложных задач, среди которых весьма важными являются, расчет характеристик времени и количества операций, требующихся для выполнения параллельных программ, и построения расписаний (планов), выполнения параллельных программ на многопроцессорных и многомашинных вычислительных системах.
Модели параллельных программ и операционные характеристики процессов их выполнения служат основой для планирования параллельных вычислительных процессов, т.е. для построения расписаний указанных процессов. Расписания параллельных вычислительных процессов определяют порядок выполнения программы на вычислительной системе, включая распределение частей программы по процессам. С увеличением числа распределяемых частей программ и количества используемых процессоров сложность построения оптимальных расписаний обычно резко возрастает. Поэтому важное значение имеют простые в построении и удобные в реализации приближенные расписания параллельных вычислительных процессов, близкие к оптимальным с точки зрения времени выполнения параллельных программ.
Постановка задачи
Имеется вычислительная система (ВС), состоящая из N несвязанных идентичных устройств (приборов, процессоров и т.п.)
На обслуживание в ВС поступает набор из M независимых параллельных заданий (работ) 
известно время решения 
задания 
на любом из устройств. При этом каждое задание может выполняться на любом из устройств (процессоре), в каждый момент времени отдельный процессор обслуживает не более одного задания и выполнение задания не прерывается для передачи на другой процессор. Требуется найти такое распределение заданий по процессорам, при котором суммарное время выполнения заданий на каждом из процессоров было бы минимальным.
Пример решения
Листинг программы
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace WindowsFormsApplication4
{
public partial class Form1: Form
{
public int[] arr;
int n;
Form2 frm2;
public void turnSort(int[] a, int l, int r)
{
int temp;
int x = a[l + (r - l) / 2];
int i = l;
int j = r;
while (i <= j)
{
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i < r)
turnSort(a, i, r);
if (l < j)
turnSort(a, l, j);
}
public Form1()
{
InitializeComponent();
frm2 = new Form2(this);
}
public void button1_Click(object sender, EventArgs e)
{
try
{
if (textBox1.Text == "" || textBox2.Text == "" || textBox3.Text == "" || textBox4.Text == "")
{
MessageBox.Show("Заполните поля");
}
else
{
button1.Enabled = false;
button2.Enabled = true;
int i = 0;
int s, f;
Random rand = new Random(DateTime.Now.Millisecond);
button1.Enabled = true;
n = int.Parse(textBox2.Text);
s = int.Parse(textBox3.Text);
f = int.Parse(textBox4.Text);
arr = new int[n];
richTextBox1.Text = "Новый массив: ";
if (s > f)
{
f = int.Parse(textBox3.Text);
s = int.Parse(textBox4.Text);
}
while (i < n)
{
arr[i] = rand.Next(s, f);
richTextBox1.Text += arr[i].ToString() + " ";
i++;
}
}
}
catch
(FormatException)
{
MessageBox.Show("Ошибка ввода");
button1.Enabled = true;
button2.Enabled = false;
}
catch (System.OverflowException)
{
MessageBox.Show("Слишком много");
}
}
public void button2_Click(object sender, EventArgs e)
{
int m;
richTextBox1.Text += "\n Сортировка";
turnSort(arr, 0, n - 1);
int i = n - 1;
while (i!= -1)
{
richTextBox1.Text += " " + arr[i];
i--;
}
m = int.Parse(textBox1.Text);
int[] G = new int[m];
i = n - 1;
int j = 0;
while (i!= -1)
{
int min = 0;
for (j = 0; j < m; j++)
{
if (G[min] > G[j])
{
min = j;
}
}
G[min] += arr[i];
i--;
}
}
public void button3_Click(object sender, EventArgs e)
{
frm2 = new Form2(this);
frm2.Refresh();
frm2.Show();
}
}
}
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace WindowsFormsApplication4
{
public partial class Form2: Form
{
public Form1 f;
public Form2(Form1 f)
{
InitializeComponent();
this.f = f;
this.AutoSize = true;
try
{
int h = Convert.ToInt32(f.textBox2.Text)+2;
int l = Convert.ToInt32(f.textBox1.Text)+1;
int m = int.Parse(f.textBox2.Text) - 1;
int[] ar = new int[h-2];
TextBox[,] tb = new TextBox[h, l];
for (int i = 0; i < h; i++)
{
for (int j = 0; j < l; j++)
{
tb[i, j] = new System.Windows.Forms.TextBox();
tb[i, j].Location = new System.Drawing.Point(100 * j, 50 + i * 30);
tb[i, j].Name = "textBox" + i.ToString();
tb[i, j].Size = new System.Drawing.Size(75, 23);
Controls.Add(tb[i, j]);
}
}
for (int i = 1; i < h - 1; i++)
{
tb[i, 0].Text = "Iter" + i;
}
for (int j = 1; j < l; j++)
{
tb[0, j].Text = "Proc" + j;
}
tb[h-1, 0].Text = "Итого";
int c = m;
int t = 0;
while (c!= -1)
{
ar[t] = f.arr[c];
c--;
t++;
}
c = 0;
int[] sum = new int[Convert.ToInt32(f.textBox1.Text)];
for (int i = 1; i < h-1; i++)
{
int minVal = sum.Min();
int j = Array.IndexOf(sum, minVal);
tb[i, j+1].Text = Convert.ToString(ar[c]);
sum[j] = sum[j]+ ar[c];
c++;
}
for (int j = 0; j < Convert.ToInt32(f.textBox1.Text); j++)
{
tb[h - 1, j + 1].Text = Convert.ToString(sum[j]);
}
}
catch (System.FormatException)
{
f.Show();
}
catch (System.NullReferenceException)
{
f.Show();
}
}
}
}
Выводы
Матрица T была упорядочена методом турнирной сортировки, так как она использует N*log(N) элементарных операций, что значительно быстрее по сравнению с простыми методами сортировки.
Использованный метод критического пути (Critical Method Path или CMP) равномерно распределяет нагрузку на устройства при условии, что на вход подаётся матрица T, упорядоченная по убыванию.
Список использованной литературы
1. Коффман Э.Г. “Теория расписания и вычислительные машины” – M.: “Наука”, 1987
- Романовский И.В. “Алгоритмы решения экстремальных задач” – М.: “Наука”, 1977
- Пашкеев С.Д., Минязов Р.И., Могилевский В.Д. “Машинные методы оптимизации в технике связи” – М.: “Связь”, 1976.