Re: Несколько потоков - быстрее вычичсление?
От: stump http://stump-workshop.blogspot.com/
Дата: 23.05.08 10:07
Оценка: +3 -2
Здравствуйте, den123, Вы писали:

D>Здравствуйте!


D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.

Прямой зависимости больше потоков — быстрее вычисление не существует. Все зависит от множества условий. Вы можете получить выигрыш в производительности если:
— алгоритм хорошо распараллеливается (одному потоку не надо ждать результатов расчета в другом потоке)
— паралельные потоки не конкурируют за доступ к одному и тому же ресурсу (диск, порт, сеть, графическая подсистема, соединение с БД, и наконец процессор)
— аппаратная платформа поддерживает паралельное исполнение (это частный случай предыдущего пункта, когда ресурс — процессор)
— накладные расходы на обеспечение параллельного исполнения не велики по сравнению с общим временем расчета.
А теперь оцените по этим критериям свою задачу.
Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.
Если же можно отделить расчеты от графического вывода, графический вывод от работы с диском или сетью, и разнести это по разным потокам, то это даст прирост производительности даже на однопроцессорной системе. Просто за счет уменьшения простоев при работе с ресурсами.
Или например, распараллеливание алгоритма поэлементного сложения двух массивов в 1000 элементов каждый на тысячу потоков. Производительность упадет на несколько порядков по сравнению с выполнением в одном потоке, за счет накладных расходов на распараллеливание.
Понедельник начинается в субботу
многопоточность
Re: Несколько потоков - быстрее вычичсление?
От: TK Лес кывт.рф
Дата: 23.05.08 10:38
Оценка: +5
Здравствуйте, den123, Вы писали:

D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.


Увеличение производительности возможно только в том случае, если это подкрелено дополнительным hardware (несколько ядер процессора/процессоров)
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Re[3]: Несколько потоков - быстрее вычичсление?
От: TfL  
Дата: 23.05.08 10:19
Оценка: 2 (1) -2
Здравствуйте, den123, Вы писали:

D>Здравствуйте, stump, Вы писали:


S>>

D>

D>Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.

D>Из предыдущих ответов я понял, что это не так — даже на однопроцессорной машине можно получить выигрыш в производительности.

D>Может я не правильно понял предыдущих товарищей?

все вы правильно поняли, в нескольких потоках будет работать быстрее, но есть верхняя граница по кол потоков и бла бла бла ..
Re[3]: Несколько потоков - быстрее вычичсление?
От: stump http://stump-workshop.blogspot.com/
Дата: 23.05.08 10:31
Оценка: 1 (1) +2
Здравствуйте, den123, Вы писали:

D>Здравствуйте, stump, Вы писали:


S>>

D>

D>Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.

D>Из предыдущих ответов я понял, что это не так — даже на однопроцессорной машине можно получить выигрыш в производительности.

D>Может я не правильно понял предыдущих товарищей?


Мы берем абстрактный случай — чисто расчетный алгоритм, который работает только с данными в стеке и куче и не вызывает никаких внешних API, например, то-же суммирование массивов. И выполняем его паралельно в двух потоках.
В одонопроцессорной системе мы гарантированно получаем снижение производительности. Потоки последовательно получают кванты времени в течении которых выполняются, плюс каждое переключение контекста потоков занимает несколько тысяч процессорных тактов. Вот это переключение контекста и дает снижение производительности. Это может быть снижение на 10% или на 0.1%, но увеличения гарантировано не будет.
Есть еще один фактор — это кэширование данных. Для оптимизации часть данных с которыми работает поток подгужается в процессорный кэш. Если к этим данным (или даже не именно к этим, а к рядом лежащим) обращаются из другого потока, они выгружаются из кэша и обращение идет непосредственно к памяти. Это еще снижает производительность. Причем даже на многоядерных системах.
Из-за этого, распаралеливая расчетна два потока мы обычно вместо 100% прироста производительности получаем 30% — 60%.
Понедельник начинается в субботу
Re[7]: Несколько потоков - быстрее вычичсление?
От: Димчанский Литва http://dimchansky.github.io/
Дата: 23.05.08 12:10
Оценка: 9 (1)
Здравствуйте, stump, Вы писали:

S>Кстати, я читал, что ParallelFX смотрит сколько ядер, и решает стоит ли рараллелить задачу.


Да, если мне не изменяет память, то именно так и сделано в Parallel FX. Мне нужна была подобная либа под .NET 2.0, так я на коленке написал свою реализацию, пусть и не полный функционал, но то, что требуется. Там тоже распараллеливание происходит реально по числу процессоров.

Parallel.cs
using System;
using System.Collections.Generic;
using System.Threading;

namespace Dimchansky.Framework.Threading
{
    /// <summary>
    /// Provides support for parallel loops and regions.
    /// </summary>
    public static class Parallel
    {
        /// <summary>
        /// Number of workers thread used in parallel computations by default.
        /// </summary>
        private static readonly int idealNumberOfThreads = Environment.ProcessorCount;

        /// <summary>
        /// Executes each of the provided actions inside a discrete, asynchronous task. 
        /// </summary>
        /// <param name="actions">An array of actions to execute.</param>
        public static void Do(params Action[] actions)
        {
            Do(idealNumberOfThreads, actions);
        }

        /// <summary>
        /// Executes each of the provided actions inside a discrete, asynchronous task. 
        /// </summary>
        /// <param name="numberOfThreads">An array of actions to execute.</param>
        /// <param name="actions">An array of actions to execute.</param>
        public static void Do(int numberOfThreads, params Action[] actions)
        {
            if (actions == null || numberOfThreads < 1)
                return;

            if (actions.Length > 0)
            {
                ForEach(actions,
                        delegate(Action a)
                        {
                            if (a != null)
                                a();
                        },
                        numberOfThreads);
            }
        }

        /// <summary>
        /// Executes a for loop in which iterations may run in parallel. 
        /// </summary>
        /// <param name="fromInclusive">The start index, inclusive.</param>
        /// <param name="toExclusive">The end index, exclusive.</param>
        /// <param name="body">The body to be invoked for each iteration.</param>
        public static void For(int fromInclusive, int toExclusive, Action<int> body)
        {
            For(fromInclusive, toExclusive, body, idealNumberOfThreads);
        }

        /// <summary>
        /// Executes a for loop in which iterations may run in parallel. 
        /// </summary>
        /// <param name="fromInclusive">The start index, inclusive.</param>
        /// <param name="toExclusive">The end index, exclusive.</param>
        /// <param name="body">The body to be invoked for each iteration.</param>
        /// <param name="numberOfThreads">Number of threads to use for executing action.</param>
        public static void For(int fromInclusive, int toExclusive, Action<int> body, int numberOfThreads)
        {
            if (fromInclusive >= toExclusive || body == null || numberOfThreads < 1)
                return;

            parallelForWorker(fromInclusive, toExclusive, body, numberOfThreads);
        }

        /// <summary>
        /// Executes an action for each item in the enumerable data source, where each element may potentially be processed in parallel.
        /// </summary>
        /// <typeparam name="T">The type of the data in the enumerable.</typeparam>
        /// <param name="source">An enumerable data source.</param>
        /// <param name="body">The action to invoke for each element in the source.</param>
        public static void ForEach<T>(IEnumerable<T> source, Action<T> body)
        {
            ForEach(source, body, idealNumberOfThreads);
        }

        /// <summary>
        /// Executes an action for each item in the enumerable data source, where each element may potentially be processed in parallel.
        /// </summary>
        /// <typeparam name="T">The type of the data in the enumerable.</typeparam>
        /// <param name="source">An enumerable data source.</param>
        /// <param name="body">The action to invoke for each element in the source.</param>
        /// <param name="numberOfThreads">Number of threads to use for executing action.</param>
        public static void ForEach<T>(IEnumerable<T> source, Action<T> body, int numberOfThreads)
        {
            if (source == null || body == null || numberOfThreads < 1)
                return;

            T[] array = source as T[];
            if (array != null)
            {
                parallelForEachWorker(array, body, numberOfThreads);
            }
            else
            {
                IList<T> list = source as IList<T>;
                if (list != null)
                {
                    parallelForEachWorker(list, body, numberOfThreads);
                }
                else
                {
                    using (IEnumerator<T> enumerator = source.GetEnumerator())
                    {
                        parallelForEachWorker(enumerator, body, numberOfThreads);
                    }
                }
            }
        }

        #region Helpers

        private static void parallelForWorker(int fromInclusive, int toExclusive, Action<int> body, int numberOfThreads)
        {
            if (toExclusive > fromInclusive)
            {
                int elementsCount = toExclusive - fromInclusive;

                // reduce workers count if possible
                int workItems = Math.Max(Math.Min(elementsCount, numberOfThreads), 1);

                // Divide the list up into chunks
                int chunkSize = Math.Max(elementsCount/workItems, 1);
                int count = workItems;

                // Use an event to wait for all work items
                using (ManualResetEvent mre = new ManualResetEvent(false))
                {
                    List<Exception> innerExceptions = null;
                    object innerExceptionsLocker = new object();

                    // Each work item processes appx 1/Nth of the data items
                    WaitCallback callback = delegate(object state)
                                                {
                                                    int iteration = (int) state;
                                                    int from = chunkSize*iteration + fromInclusive;
                                                    int to = iteration == workItems - 1
                                                                 ? toExclusive
                                                                 : chunkSize*(iteration + 1) + fromInclusive;

                                                    while (from < to)
                                                    {
                                                        try
                                                        {
                                                            body(from++);
                                                        }
                                                        catch (Exception exception)
                                                        {
                                                            lock (innerExceptionsLocker)
                                                            {
                                                                if (innerExceptions == null)
                                                                {
                                                                    innerExceptions = new List<Exception>();
                                                                }
                                                                innerExceptions.Add(exception);
                                                            }
                                                            break;
                                                        }
                                                    }

                                                    if (Interlocked.Decrement(ref count) == 0)
                                                        mre.Set();
                                                };

                    // The ThreadPool is used to process all but one of the 
                    // chunks; the current thread is used for that chunk, 
                    // rather than just blocking.
                    for (int i = 0; i < workItems - 1; i++)
                    {
                        ThreadPool.QueueUserWorkItem(callback, i);
                    }

                    try
                    {
                        callback(workItems - 1);
                    }
                    catch (Exception exception)
                    {
                        lock (innerExceptionsLocker)
                        {
                            if (innerExceptions == null)
                            {
                                innerExceptions = new List<Exception>();
                            }
                            innerExceptions.Add(exception);
                        }
                    }

                    // Wait for all work to complete
                    mre.WaitOne();

                    if (innerExceptions != null)
                    {
                        throw new AggregateException(innerExceptions);
                    }
                }
            }
        }

        private static void parallelForEachWorker<T>(T[] array, Action<T> body, int numberOfThreads)
        {
            int lowerBound = array.GetLowerBound(0);
            int toExclusive = array.GetUpperBound(0) + 1;

            parallelForWorker(lowerBound, toExclusive,
                              delegate(int i) { body(array[i]); }, numberOfThreads);
        }

        private static void parallelForEachWorker<T>(IList<T> list, Action<T> body, int numberOfThreads)
        {
            parallelForWorker(0, list.Count, delegate(int i) { body(list[i]); }, numberOfThreads);
        }

        private static void parallelForEachWorker<T>(IEnumerator<T> enumerator, Action<T> action, int numberOfThreads)
        {
            int count = numberOfThreads;

            // Use an event to wait for all work items to complete
            using (ManualResetEvent mre = new ManualResetEvent(false))
            {
                List<Exception> innerExceptions = null;
                object innerExceptionsLocker = new object();

                // Each work item will continually pull data from the 
                // enumerator and process it until there is no more data
                // to process
                WaitCallback callback = delegate
                                            {
                                                while (true)
                                                {
                                                    T data;
                                                    lock (enumerator)
                                                    {
                                                        if (!enumerator.MoveNext()) break;
                                                        data = enumerator.Current;
                                                    }

                                                    try
                                                    {
                                                        action(data);
                                                    }
                                                    catch (Exception exception)
                                                    {
                                                        lock (innerExceptionsLocker)
                                                        {
                                                            if (innerExceptions == null)
                                                            {
                                                                innerExceptions = new List<Exception>();
                                                            }
                                                            innerExceptions.Add(exception);
                                                        }
                                                        break;
                                                    }
                                                }

                                                if (Interlocked.Decrement(ref count) == 0)
                                                    mre.Set();
                                            };

                // The ThreadPool is used to process all but one of the 
                // chunks; the current  thread is used for that chunk, 
                // rather than just blocking.
                for (int i = 0; i < numberOfThreads - 1; i++)
                {
                    ThreadPool.QueueUserWorkItem(callback, i);
                }

                try
                {
                    callback(numberOfThreads - 1);
                }
                catch (Exception exception)
                {
                    lock (innerExceptionsLocker)
                    {
                        if (innerExceptions == null)
                        {
                            innerExceptions = new List<Exception>();
                        }
                        innerExceptions.Add(exception);
                    }
                }

                // Wait for all work to complete
                mre.WaitOne();

                if (innerExceptions != null)
                {
                    throw new AggregateException(innerExceptions);
                }
            }
        }

        #endregion
    }
}


AggregateException.cs — беспощадно выдрал из Parallel FX
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Runtime.Serialization;
using System.Security.Permissions;

namespace Dimchansky.Framework.Threading
{
    public delegate TResult Func<T, TResult>(T arg);

    [Serializable, DebuggerDisplay("Count = {InnerExceptions.Count}")]
    public class AggregateException : Exception
    {
        // Fields
        private Exception[] m_innerExceptions;

        // Methods
        public AggregateException()
        {
        }

        public AggregateException(IEnumerable<Exception> innerExceptions)
            : this(null, innerExceptions)
        {
        }

        public AggregateException(string message)
            : base(message)
        {
        }

        [SecurityPermission(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
        protected AggregateException(SerializationInfo info, StreamingContext context)
            : base(info, context)
        {
        }

        public AggregateException(string message, IEnumerable<Exception> innerExceptions)
            : this(message, (innerExceptions == null) ? null : new List<Exception>(innerExceptions))
        {
        }

        private AggregateException(string message, List<Exception> innerExceptions)
            : base(message, ((innerExceptions != null) && (innerExceptions.Count > 0)) ? innerExceptions[0] : null)
        {
            if (innerExceptions == null)
            {
                throw new ArgumentNullException("innerExceptions");
            }
            this.m_innerExceptions = innerExceptions.ToArray();
            for (int i = 0; i < this.m_innerExceptions.Length; i++)
            {
                if (this.m_innerExceptions[i] == null)
                {
                    throw new ArgumentException("An element of innerExceptions was null.");
                }
            }
        }

        public AggregateException(string message, Exception inner)
            : this(message, new Exception[] { inner })
        {
        }

        public AggregateException Flatten(params AggregateException[] exceptions)
        {
            if (exceptions == null)
            {
                throw new ArgumentNullException("exceptions");
            }
            List<Exception> list = new List<Exception>(this.m_innerExceptions);
            AggregateException[] exceptionArray = (AggregateException[])exceptions.Clone();
            for (int i = 0; i < exceptionArray.Length; i++)
            {
                if (exceptionArray[i] == null)
                {
                    throw new ArgumentException("An element in exceptions was null.");
                }
                list.AddRange(exceptionArray[i].InnerExceptions);
            }
            return new AggregateException(this.Message, list.ToArray());
        }

        public void Handle(Func<Exception, bool> handler)
        {
            if (handler == null)
            {
                throw new ArgumentNullException("handler");
            }
            List<Exception> list = null;
            for (int i = 0; i < this.m_innerExceptions.Length; i++)
            {
                if (!handler(this.m_innerExceptions[i]))
                {
                    if (list == null)
                    {
                        list = new List<Exception>();
                    }
                    list.Add(this.m_innerExceptions[i]);
                }
            }
            if (list != null)
            {
                throw new AggregateException(this.Message, list.ToArray());
            }
        }

        public override string ToString()
        {
            string str = base.ToString();
            for (int i = 0; i < this.m_innerExceptions.Length; i++)
            {
                str = string.Format("{0}{1}---> (Inner Exception #{2}) {3}{4}{5}", new object[] { str, Environment.NewLine, i, this.m_innerExceptions[i].ToString(), "<---", Environment.NewLine });
            }
            return str;
        }

        // Properties
        public ReadOnlyCollection<Exception> InnerExceptions
        {
            get
            {
                return new ReadOnlyCollection<Exception>(this.m_innerExceptions);
            }
        }
    }
}


Пример обработки исключений приводил уже здесь
Автор: Димчанский
Дата: 28.02.08
.

Пример распареллеливания кода.
Было:
for (int i = 0; i < 100; i++) { 
  a[i] = a[i]*a[i]; 
}


Стало:
Parallel.For(0, 100, delegate(int i) { 
  a[i] = a[i]*a[i]; 
});
Re[3]: Несколько потоков - быстрее вычичсление?
От: TfL  
Дата: 23.05.08 08:44
Оценка: 3 (1)
Здравствуйте, den123, Вы писали:

D>Здравствуйте, TfL, Вы писали:


D>...

TfL>>Конечно можно.
D>Если можно в двух словах — за счет чего? Просто идею.

Насколько я осведомлен, у основного потока есть приоритет и ОС выделяет определенный квант.. нето времени .. нето ресурса

Если мы разбиваем вычисление на несколько потоков, соотв получаем больше выч ресурса,

Но 1. есть лимит по кол потоков после чего выигрыш переростает в проигрыш ..
2. проблемы синхронизации + усложнение логики прогр
3. тонкости реализации многопоточности в ОС ..
Re: Несколько потоков - быстрее вычичсление?
От: TfL  
Дата: 23.05.08 08:12
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Здравствуйте!


D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.


Конечно можно. Но есть лимит по кол потоков. Помниться даже рекоминдации были не более 4-6 потоков. Дальше система начинает деградировать.
Соотв и алгоритма может зависть, но это уж ваша математика.
Re: Несколько потоков - быстрее вычичсление?
От: tyger Россия  
Дата: 23.05.08 08:49
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Здравствуйте!


D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.


Конечно можно! Особенно если на системе многоядерный процессор или хотябы с технологией HyperThrading... Где-то здесь даже тест пробегал по производительности.

Если вычисления незвисимые или почти независимые, то на любой системе должен быть прирост. Если пользоваться потоками .NET, то они сами будут раскиданы по разным ядрам...
Re[3]: Несколько потоков - быстрее вычичсление?
От: vmpire Россия  
Дата: 23.05.08 09:06
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Здравствуйте, TfL, Вы писали:


D>...

TfL>>Конечно можно.
D>Если можно в двух словах — за счет чего? Просто идею.

Я думаю, за счёт того что почти все современные процессоры многопоточные — несколько ядер или, хотя бы, hyperthreading.
В этом случае потоки будут выполняться параллельно.

Плюс, даже на одном процессоре можно получить выигрыш в некоторых случаях. Например, если один поток ждёт окончания ввода/вывода, другой в это время может что-то считать.
Re: Несколько потоков - быстрее вычичсление?
От: Димчанский Литва http://dimchansky.github.io/
Дата: 23.05.08 09:54
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.


Если есть возможность использовать .NET Framework 3.5, то рекомендую посмотрет на Parallel FX библиотеку от MS. Очень удобно быстро распараллелить всякие for циклы. Если .NET Framework 2.0, то могу сюда выложить аналог той библиотеки (мой велосипед ).
Re[3]: Несколько потоков - быстрее вычичсление?
От: Димчанский Литва http://dimchansky.github.io/
Дата: 23.05.08 10:29
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Спасибо! В библиотеке нет необходимости. Во всяком случае пока. На данном этапе мне важно было понять лишь возможность такого "ускорения" и идею.


Понял. На мой взгляд ускорение будет заметное (в зависимости от распараллелености алгоритма), если в процессоре не одно ядро или он гипертрединг поддерживает. Если там одно ядро без гипертрединга, то сомневаюсь, что в каких-то массивных вычисления будет ускорение, скорее наоборот некоторое падение производительности из-за оверхеда связанного с синхронизацией.
Re[5]: Несколько потоков - быстрее вычичсление?
От: Димчанский Литва http://dimchansky.github.io/
Дата: 23.05.08 11:42
Оценка: 2 (1)
Здравствуйте, den123, Вы писали:

D>Если в число таких задач поставить другие мои потоки, то в целом моя задача получит бОльшее количество квантов времени на выполнение.


Ну мне лично это смахивает не некую попытку хака, чтобы заработать на этом копейку и то вопрос, заработаешь ли. С одной стороны да, твоим потокам больше времени будет уделятся, с другой стороны синхронизация на однопроцессорной машине сожрет это преимущество.
Не проще ли тогда просто Real Time приоритет своему потоку сделать на однопроцессорной машине?

Ну а глядя в будущее и не особо запариваясь об однопроцессорных машинах, лучше начать параллелить сейчас, осознавая, что на однопроцессроной будет потеря в производительности, зато на паре ядер можно ожидать прироста.
Re[6]: Несколько потоков - быстрее вычичсление?
От: stump http://stump-workshop.blogspot.com/
Дата: 23.05.08 11:46
Оценка: 2 (1)
Здравствуйте, Димчанский, Вы писали:

Д>Здравствуйте, den123, Вы писали:


D>>Если в число таких задач поставить другие мои потоки, то в целом моя задача получит бОльшее количество квантов времени на выполнение.


Д>Ну мне лично это смахивает не некую попытку хака, чтобы заработать на этом копейку и то вопрос, заработаешь ли. С одной стороны да, твоим потокам больше времени будет уделятся, с другой стороны синхронизация на однопроцессорной машине сожрет это преимущество.

Д>Не проще ли тогда просто Real Time приоритет своему потоку сделать на однопроцессорной машине?

Д>Ну а глядя в будущее и не особо запариваясь об однопроцессорных машинах, лучше начать параллелить сейчас, осознавая, что на однопроцессроной будет потеря в производительности, зато на паре ядер можно ожидать прироста.


Кстати, я читал, что ParallelFX смотрит сколько ядер, и решает стоит ли рараллелить задачу.
Понедельник начинается в субботу
Re[4]: Несколько потоков - быстрее вычичсление?
От: stump http://stump-workshop.blogspot.com/
Дата: 23.05.08 10:34
Оценка: +1
Здравствуйте, TfL, Вы писали:

TfL>Здравствуйте, den123, Вы писали:


D>>Здравствуйте, stump, Вы писали:


S>>>

D>>

D>>Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.

D>>Из предыдущих ответов я понял, что это не так — даже на однопроцессорной машине можно получить выигрыш в производительности.

D>>Может я не правильно понял предыдущих товарищей?

TfL>все вы правильно поняли, в нескольких потоках будет работать быстрее, но есть верхняя граница по кол потоков и бла бла бла ..
Объясните откуда прирост берется. На пальцах. Без бла бла бла...
Понедельник начинается в субботу
Re[4]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 11:03
Оценка: -1
Здравствуйте, stump, Вы писали:


S>Мы берем абстрактный случай — чисто расчетный алгоритм, который работает только с данными в стеке и куче и не вызывает никаких внешних API, например, то-же суммирование массивов. И выполняем его паралельно в двух потоках.
S>В одонопроцессорной системе мы гарантированно получаем снижение производительности. Потоки последовательно получают кванты времени в течении которых выполняются, плюс каждое переключение контекста потоков занимает несколько тысяч процессорных тактов. Вот это переключение контекста и дает снижение производительности. Это может быть снижение на 10% или на 0.1%, но увеличения гарантировано не будет.
S>Есть еще один фактор — это кэширование данных. Для оптимизации часть данных с которыми работает поток подгужается в процессорный кэш. Если к этим данным (или даже не именно к этим, а к рядом лежащим) обращаются из другого потока, они выгружаются из кэша и обращение идет непосредственно к памяти. Это еще снижает производительность. Причем даже на многоядерных системах.
S>Из-за этого, распаралеливая расчетна два потока мы обычно вместо 100% прироста производительности получаем 30% — 60%.

Я думаю, что Вы абсолютно правы, если на машине НИЧЕГО ДРУГОГО не выполняется. Т.е. если есть только одна задача — моя, то любое разбиение чисто вычислительной задачи на потоки только вызовет потерю производительности из-за накладных расходов на переключения и т.п. Однако, если на машине выполняется много других задач, то можно получить выигрыш производительности. ОС все равно будет прерывать мою задачу/мой поток, чтобы дать очередной квант времени какой-то другой задаче. Если в число таких задач поставить другие мои потоки, то в целом моя задача получит бОльшее количество квантов времени на выполнение. Разумеется, что разбиение на N потоков не принесет увелечения производительности в N раз.
WBR — Yuriy
Re[3]: Несколько потоков - быстрее вычичсление?
От: Nonmanual Worker  
Дата: 23.05.08 11:03
Оценка: -1
Здравствуйте, den123, Вы писали:

D>Из предыдущих ответов я понял, что это не так — даже на однопроцессорной машине можно получить выигрыш в производительности.


D>Может я не правильно понял предыдущих товарищей?


stump вам все четко и верно расписал.
На многопроцессорной системе будет выигрыш однозначно, в идеале во столько раз, сколько процессоров (но реально конечно немного меньше).
На однопроцессорной машине, для чисто расчетной задачи, будет падение суммарной производительности при распараллеривании, и чем больше потоков — тем сильнее падение. На сколько % — сказать не могу. Однако, гипотетически, если одновременно работает несколько процессороемких задач помимо вашей, то возможен небольшой прирост производительности за счет вытеснения других задач.
Поэтому определяйте сколько ядер — делайте столько же потоков — и вперед.
Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 08:00
Оценка:
Здравствуйте!

Среда — Windows, на машине выполняется много приложений. Можно ли ускорить вычисление некоторого алгоритма, если рзбить вычисление на несколько потоков? Каждый поток выполняет свою часть вычислений, это допускается алгоритмом.
WBR — Yuriy
Re[2]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 08:16
Оценка:
Здравствуйте, TfL, Вы писали:

...
TfL>Конечно можно.
Если можно в двух словах — за счет чего? Просто идею.
WBR — Yuriy
Re[4]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 08:49
Оценка:
Здравствуйте, TfL, Вы писали:
Спасибо TfL!
Идея понятна, спасибо!
WBR — Yuriy
Re[2]: Несколько потоков - быстрее вычичсление?
От: vasmann  
Дата: 23.05.08 08:58
Оценка:
Здравствуйте, tyger, Вы писали:

T>Если вычисления незвисимые или почти независимые, то на любой системе должен быть прирост. Если пользоваться потоками .NET, то они сами будут раскиданы по разным ядрам...


Всегда думал что ОС занимается распределнием нагрузки на ядра/процессоры ...
Re[2]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 10:08
Оценка:
Здравствуйте, Димчанский, Вы писали:

...

Д>Если есть возможность использовать .NET Framework 3.5, то рекомендую посмотрет на Parallel FX библиотеку от MS. Очень удобно быстро распараллелить всякие for циклы. Если .NET Framework 2.0, то могу сюда выложить аналог той библиотеки (мой велосипед ).


Спасибо! В библиотеке нет необходимости. Во всяком случае пока. На данном этапе мне важно было понять лишь возможность такого "ускорения" и идею.
WBR — Yuriy
Re[2]: Несколько потоков - быстрее вычичсление?
От: den123 Израиль http://den123.smugmug.com
Дата: 23.05.08 10:14
Оценка:
Здравствуйте, stump, Вы писали:

S>

Например, распараллеливание чисто расчетного алгоритма, который не взаимодействует ни с графической подсистемой ни с диском, на однопроцессорной системе приведет к снижению производительности.

Из предыдущих ответов я понял, что это не так — даже на однопроцессорной машине можно получить выигрыш в производительности.

Может я не правильно понял предыдущих товарищей?
WBR — Yuriy
Re[4]: Несколько потоков - быстрее вычичсление?
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 23.05.08 12:34
Оценка:
Здравствуйте, stump, Вы писали:

S>плюс каждое переключение контекста потоков занимает несколько тысяч процессорных тактов.


Переключение контекстов происходит вне зависимости от количества потоков, просто по таймеру. Но время между переключениями контекста для современного процессора это просто вечность.

S>Есть еще один фактор — это кэширование данных. Для оптимизации часть данных с которыми работает поток подгужается в процессорный кэш. Если к этим данным (или даже не именно к этим, а к рядом лежащим) обращаются из другого потока, они выгружаются из кэша и обращение идет непосредственно к памяти.


А вот этот факт имеет место быть.
... <<RSDN@Home 1.2.0 alpha 4 rev. 1082 on Windows Vista 6.0.6001.65536>>
AVK Blog
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.