Автор работы: Пользователь скрыл имя, 21 Января 2013 в 03:16, задача
В данном расчетно-графическом задании проводится распараллеливание вычислительных процессов с целью закрепления теоретических знаний в области теории распараллеливания вычислительных алгоритмов, формирования практических умений и навыков разработки программного средства для распараллеливания вычислительных алгоритмов и закрепления практических навыков самостоятельного решения инженерных задач, развития творческих способностей и умений пользоваться технической, нормативной и справочной литературой.
Введение 3
1 Теоретические предпосылки поставленной проблемы 4
2 Разработка программного средства 16
Заключение 24
Список использованных источников 25
Приложение А – Текст программы 26
Приложение Б – Контрольный пример 31
for (int x = 1; x < sz; x++)
if (S[i, x] + S[j, x] > 0)
else S[i, x] = 0;
}
public void FillMatrN()
{
for (int j = 1, t = 0; j < sz; j++)
{
for (int i = j; i < sz; i++)
if (mtr[i, j] > 2)
{
t = i;
for (int x = j; x < sz; x++)
if ((mtr[x, j] > 2) && (x != t))
{
L[x, t] = 1;
}
}
}
//------------------
int[,] Lt = new int[sz, sz];
List<List<int>> C = new List<List<int>>();
List<int> uni = new List<int>();
List<int> inter = new List<int>();
for (int i = 1; i < sz; i++, C.Clear(), uni.Clear(), inter.Clear())
{
for (int j = 1; j < sz; j++)
if (mtr[i, j] > 0)
{
C.AddVertex(new List<int>());
for (int x = 0; x < sz; x++)
if (L[j, x] == 1)
}
//union
if (C.Count == 1)
foreach (int nt in C[0])
L[i, nt] = L[nt, i] = 1;
else
if (C.Count > 0)
{
IEnumerable<int> both;
both = C[0];
foreach (List<int> lst in C)
{
both = both.Intersect(lst);
}
foreach (int it in both)
L[it, i] = L[i, it] = 1;
}
}
}
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++)
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)
{
break;
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 – Нахождение поздних сроков выполнения алгоритма
Информация о работе Распараллеливание вычислительных алгоритмов