Форум программистов, компьютерный форум, киберфорум
C# .NET
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
0 / 0 / 0
Регистрация: 26.12.2013
Сообщений: 25
1

Параллельный метод резолюции

16.06.2015, 18:11. Показов 2009. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Привет!

Во вложениях 2 картинки с алгоритмом. По идее он должен быть параллельным. На данный момент я его реализовал для высказываний. Но то ли я в чем-то неправ во время реализации, то ли в алгоритме какая-то проблема, но у меня он не работает параллельно. Создает заданное количество нитей и вроде бы переходит из одной нити в другую, но в диспетчере задач загружен только один процессор. Отсюда первый вопрос: подскажите, пожалуйста, в чем ошибка при распараллеливании.

А второй вопрос в том, что необходимо теперь алгоритм дополнить до работы с предикатами, в частности, чтобы методом резолюции решить задачу Steamroller. Видимо нужно вести какой-то подсчет скобок и дробить дизъюнкты еще сильнее, для того чтобы можно было выполнять подстановки?

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
 
namespace ParallelResolution
{
    class Program
    {
        public static readonly List<Resolution> CL = new List<Resolution>();
        public static readonly List<Thread> WaitingThreads = new List<Thread>();  // Очередь ожидающих нитей
        public static int LastSentForResolving = 0;
        public static int LastAdded;
        public static Semaphore Sem;
 
        static void Main(string[] args)
        {
            var m = Convert.ToInt32(args[1]);
            string[] s;
            Sem = new Semaphore(1, 1);
            using (var sr = new StreamReader(args[0]))
            {
                s = sr.ReadToEnd().Trim().Split(new[] { "," }, StringSplitOptions.RemoveEmptyEntries);
            }
            for (int i = 0; i < s.Length; i++)
            {
                var res = new Resolution
                {
                    Disjuncts = s[i].Split(new[] { "v" }, StringSplitOptions.RemoveEmptyEntries).ToList()
                };
                CL.Add(res);
            }
            LastAdded = CL.Count;
            var startingTime = DateTime.Now;
            var threadList = new List<Thread>();
            //Execution();
            for (int i = 0; i < m; i++)
            {
                threadList.Add(new Thread(Execution));
                threadList[i].Start();
            }
            foreach (var thread in threadList)
            {
                thread.Join();
            }
            Console.WriteLine("Time = "+(DateTime.Now-startingTime).ToString("g"));
            Console.WriteLine("Очередь дизъюнктов:");
            foreach (var resolution in CL)
            {
                foreach (var dis in resolution.Disjuncts)
                {
                    if(resolution.Disjuncts[resolution.Disjuncts.Count-1]==dis)
                        Console.Write(dis+", ");
                    else
                    {
                        Console.Write(dis+"v");
                    }
                }
            }
        }
 
        public static async void Execution()
        {
            while (true)
            {
                if (CL.Exists(res => res.Disjuncts.SequenceEqual(new[] { "empty" }.ToList())))
                    return;
                Sem.WaitOne();
                if (LastSentForResolving == LastAdded)
                {
                    Sem.Release();
                    WaitingThreads.Add(Thread.CurrentThread);
                    //Thread.CurrentThread.Suspend();
                    continue;
                }
                var number = LastSentForResolving + 1;/*
                if (number >= CL.Count)
                {
                    Console.WriteLine("Высказывание не может быть выведено из существующих дизъюнктов.");
                    Thread.CurrentThread.Abort();
                }*/
                LastSentForResolving++;
                var i = 0;
                while (true)
                {
                    if (i >= number)
                    {
                        Sem.Release();
                        break;
                    }
                    else
                    {
                        var newDisj = Resolve(CL[i].Disjuncts, CL[number].Disjuncts);
                        var oldCount = CL.Count;
                        if (!CL.Exists(res=>res.Disjuncts.SequenceEqual(newDisj)) && newDisj.Any())
                        {
                            CL.Add(new Resolution(){Disjuncts=newDisj});
                        }
                        var newCount = CL.Count;
                        LastAdded = newCount;
                        if (newCount > oldCount && WaitingThreads.Any())
                        {
                            Sem.Release();
                            var tempThread = WaitingThreads[0];
                            WaitingThreads.Remove(tempThread);
                            //tempThread.Resume();
                        }
                        else
                        {
                            i++;
                            if (CL.Exists(res => res.Disjuncts.SequenceEqual(new[] { "empty" }.ToList())))
                            {
                                Sem.Release();
                                break;
                            }
                        }
                    }
                }
                //Thread.CurrentThread.Abort();
            }
        }
 
        static List<string> Resolve(List<string> c1, List<string> c2)
        {
            var tempC1 = new List<string>();
            tempC1.AddRange(c1);
            var tempC2 = new List<string>();
            tempC2.AddRange(c2);
            var s1 = new List<string>();
            var s2 = new List<string>();
            var newDisjunkt = new List<string>();
            var have = false;
            foreach (var dis1 in tempC1)
            {
                foreach (var dis2 in tempC2)
                {
                    if (dis1 == "-" + dis2 || "-" + dis1 == dis2)
                    {
                        s1.Add(dis1);
                        s2.Add(dis2);
                        have = true;
                        break;
                    }
                    
                }
            }
            if (have)
            {
                foreach (var dis1 in s1) //удаляем контрарные пары
                {
                    tempC1.Remove(dis1);
                }
                foreach (var dis2 in s2)
                {
                    tempC2.Remove(dis2);
                }
                if (!tempC1.Any()&&!tempC2.Any()) // если оба списка после удаления контрарных пар пустые, возвращаем пустой дизъюнкт
                {
                    newDisjunkt.Add("empty");
                    return newDisjunkt;
                }
                if (tempC1.Any())
                {
                    newDisjunkt.AddRange(tempC1);
                }
                if (tempC2.Any())
                {
                    newDisjunkt.AddRange(tempC2);
                }
                return newDisjunkt; // иначе возвращаем резольвенту
            }
            return new List<string>(); // если контрарных пар не было, возвращаем пустой список, что значит перейти далее
        }
    }
 
    class Resolution
    {
        public List<string> Disjuncts;
    }
}
Миниатюры
Параллельный метод резолюции   Параллельный метод резолюции  
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.06.2015, 18:11
Ответы с готовыми решениями:

Задача, метод резолюции
в общем само условие: Некоторые улитки являются горами. Все горы любят кошек. Значит, все улитки...

Предикаты и метод резолюции
Ребят, помогите, пожалуйста, последний зачет остался, вообще в этом не шарю.. Чтобы не...

Проверка истинности. Метод резолюции
(А→В), (В→С), (С→D), A &amp; B ├ B&amp;D //как решать подобное я вообще не знаю, но кажется используется...

Преобразовать теоремы в вопросы и получить ответы (метод резолюции)
Добрый вечер. Помогите преобразовать теоремы в вопросы и получить ответы. 1.1. А1: Если пассажир...

3
Эксперт .NET
5534 / 4298 / 1217
Регистрация: 12.10.2013
Сообщений: 12,332
Записей в блоге: 2
16.06.2015, 21:21 2
Цитата Сообщение от BJIag Посмотреть сообщение
По идее он должен быть параллельным.
BJIag, может стоит посмотреть в сторону TaskParallelLibrary?
0
0 / 0 / 0
Регистрация: 26.12.2013
Сообщений: 25
16.06.2015, 22:13  [ТС] 3
К сожалению нет. По условиям задачи необходимо варьировать количество нитей, для оценки степени параллелизма. А при использование Task'ов количество нитей не равно количеству Task'ов. И соответственно невозможно проследить насколько изменяется время выполнения в зависимости от количества нитей.
0
Master of Orion
Эксперт .NET
6098 / 4954 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
17.06.2015, 13:09 4
BJIag, TPL позволяет задать количество потоков, в котором работает код.
0
17.06.2015, 13:09
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.06.2015, 13:09
Помогаю со студенческими работами здесь

Параллельный алгоритм столбцово-ориентированный метод гаусса. MPI
Пока писал алгоритм, долго мучался инфы по столбцовому алгоритму нигде нет. В итоге написал сам,...

Смена резолюции экрана
Есть ли какая-то возможность изменить резолюцию экрана на клиенте? Проблема такая: у разработчика...

Автоматическая подстрояка к резолюции экрана.
У меня экрaн 800x600 Вoпрoс кaк сделaть чтoбы нa кoпмaх с другoй резoлюцией прoгрaммa...

Проверить общезначимость формулы методом резолюции
Здравствуйте, помогите решить, пожалуйста!


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru