Автор работы: Пользователь скрыл имя, 27 Мая 2013 в 21:11, практическая работа
Цель расчетно-графического задания:
- закрепление теоретических знаний в области теории распараллеливания вычислительных алгоритмов;
- формирование практических умений и навыков разработки программного средства для распараллеливания вычислительных алгоритмов;
- закрепление практических навыков самостоятельного решения инженерных задач, развитие творческих способностей студентов и умений пользоваться технической, нормативной и справочной литературой.
Введение 3
1 Теоретические предпосылки поставленной проблемы 5
2 Разработка программного средства 12
2.1 Постановка задачи 12
2.2 Спецификация основных процедур и функций 13
2.3 Спецификация данных 14
2.3.1 Структура входных данных 15
2.4 Разработка алгоритма решения задачи 15
2.4.1 Укрупненная схема алгоритма программного средства 15
2.5 Установка и эксплуатация программного средства 16
2.6 Работа с программным средством 16
Заключение 19
Список использованных источников 20
Приложение А – Текст программы 21
Приложение Б – Контрольный пример 31
public void Fill_N()
{
for (int i = 0; i < sz; i++)
for (int j = 0; j < sz; j++)
{
if (S[i, j] == 1) S[j, i] = 1;
if (S[i, j] + L[i, j] > 0)
N[i, j] = N[j, i] = 1;
}
}
//---
public void GetVNO()
{
//step1
//step2
B.AddVertex(1);
for (int i = 0; i < sz; i++)
C[i] = N[1, i];
//step3
bool flag = false;
int starti = 2;
do
{
for (int i = starti; i < sz; i++)
{
//step4
D.Clear();
foreach (var t in B) D.AddVertex(t);
D.AddVertex(i);
for (int j = 0; j < sz; j++)
if (C[j] + N[i, j] > 0)
E[j] = 1;
else
E[j] = 0;
//step5
bool ff = false, fff = true;
foreach (int item in D)
if (E[item] != 0)
{
fff = false;
break;
}
if (!fff) continue;
B.Clear();
foreach (var tt in D)
B.AddVertex(tt);
for (int x = 0; x < sz; x++)
C[x] = E[x];
for (int j = 1; j < sz; j++)
if ((E[j] == 0) && (!D.Contains(j)))
//step6
ff = true;
if (ff) continue;
}
//step 7
//step 9
if (A.Count < B.Count)
{
A.Clear();
foreach (var t in B)
A.AddVertex(t);
}
//step 10
flag = false;
for (int x = B.Count - 1, m = sz - 1; x >= 0; x--, m--)
if (B[x] != m)
{
//step 11
flag = true;
int sm = B[x];
B.RemoveRange(x, B.Count - x);
//step 12
for (int xx = 0; xx < sz; xx++) C[xx] = 0;
foreach (int item in B)
for (int xx = 0; xx < sz; xx++)
else C[xx] = 0;
starti = sm + 1;
break;
}
} while (flag);
//step 8 goto 4
}
public int FindFT()
{
for (int i = 0; i < sz; i++) Tau[i] = 0;
for (int i = 1; i <= Get_size(); i++)
{
if (!nd[i - 1].selected) continue;
List<int> ls = new List<int>();
for (int j = 1; j < i; j++)
{
if (nd[j - 1].selected)
if (S[i, j] == 1) ls.AddVertex(j);
}
if (ls.Count == 0)
Tau[i] = T[i];
else
{
int max = 0;
foreach (var it in ls)
if (Tau[it] > max) max = Tau[it];
Tau[i] = T[i] + max;
}
ls.Clear();
}
int maxx = 0;
foreach (var i in Tau)
if (maxx < i) maxx = i;
return maxx;
}
public void FindLT(int MaxT)
{
for (int i = 0; i < sz; i++) LTau[i] = 0;
for (int i = Get_size(); i >0; i--)
{
List<int> ls = new List<int>();
for (int j = 1; j <=Get_size(); j++)
{
if (nd[j-1].selected)
if (mtr[j, i] == 1)
ls.AddVertex(j);
}
if (ls.Count == 0)
LTau[i] = MaxT;
else
{
int min = MaxT;
foreach (var it in ls)
if (LTau[it] - T[it] < min) min = LTau[it] - T[it];
LTau[i] = min;
}
ls.Clear();
}
}
public void Renum()
{
int siz = Get_size();
for (int i = siz; i > 0; i--)
for (int j = i - 1; j > 0; j--)
for (int x = siz; x >= i; x--)
if (mtr[j,x] > 0)
{
Swap(j, i);
foreach(var i1 in nd)
if (i1.num == j)
break;
}
}
public void Swap(int x, int y)
{
int siz=mtr.GetLength(1);
int tmp;
for (int i = 0; i < siz; i++)
{
tmp=mtr[i,x];
mtr[i, x] = mtr[i, y];
mtr[i, y] = tmp;
}
for (int i = 0; i < siz; i++)
{
tmp = mtr[x, i];
mtr[x, i] = mtr[y, i];
mtr[y, i] = tmp;
}
}
}
}
Приложение Б – Контрольный пример
Рисунок 9 – Граф-схема алгоритма
Рисунок 10 – Нахождение ранних сроков выполнения алгоритма
Рисунок 11 – Нахождение поздних сроков выполнения алгоритма
Информация о работе Распараллеливание вычислительных алгоритмов