Распараллеливание вычислительных алгоритмов

Автор работы: Пользователь скрыл имя, 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

Вложенные файлы: 1 файл

Отчет РГЗ по ТВП (вариант 4).doc

— 586.50 Кб (Скачать файл)

        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++)

                                if (C[xx] + mtr[item, xx] > 0)

                                    C[xx] = 1;

                                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)

                                {

                                    foreach (var i2 in nd)

                                        if (i2.num == i)

                                        {

                                            i1.num = i;

                                            i2.num = j;

                                            break;

                                        }

                                    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 – Нахождение поздних сроков выполнения алгоритма




Информация о работе Распараллеливание вычислительных алгоритмов