ОБЪЕКТИВНОСТЬ БЕЗ КОМПРОМИССОВОбъективность Без Компромиссов В Мире Компьютеров
НОВОСТИ САЙТАТЕСТИРУЕМ ВМЕСТЕИНТЕРНЕТ и ПОВСЯКО-РАЗНОСОФТ ПРОЕКТЫНАШИ ССЫЛКИ
ГЛАВНАЯ >> ТЕСТИРУЕМ ВМЕСТЕ >> ПРОЦЕССОРЫ: Многопоточный код своими руками

НАЗВАНИЕ СТАТЬИ: Многопоточный код своими руками
АВТОРСТВО: Алекс Наб
ДАТА НАПИСАНИЯ: Февраль 2007 года
ДАТА ПЕЧАТНОЙ ПУБЛИКАЦИИ: Апрель 2007 года ( ISSN 0235-3520 )
ДАТА ПОСЛЕДНЕЙ РЕДАКЦИИ: Февраль 2007 года
Алекс Н.

СОДЕРЖАНИЕ

  • Вступление
  • Алгоритм студента XX века
  • Алгоритм студента XXI века
  • Взглянув на экран
  • Таблица результатов выполнения компиляций
  • РАЗМАХАЙКА: Далеко ходить не надо
  • РАЗМАХАЙКА: Позвольте напомнить
  • РАЗМАХАЙКА: Листинг 1
  • РАЗМАХАЙКА: Листинг 2

    Увеличение количества вычислительных компонентов в центральном процессоре способствует интенсивному развитию технологий многопоточного программирования. Однако эффективное управление потоками дело хлопотное и не во всех случаях приводит к росту производительности.
    В частности, нет большого смысла в попытках мультипрограммирования решета Эратосфена, поскольку в нем натуральный ряд отбирается постепенным отсеиванием составных чисел. Или, например, алгоритм определения некоторого числа из ряда Фибоначчи не удастся сделать многопоточным, так как каждый последующий член ряда равен сумме двух предыдущих, а значит, надо шаг за шагом определять весь ряд. Да и ни к чему "параллелить" алгоритм определения факториала (n!=1*2*3*...*n), поскольку факториал числа 65 вычисляется за считаные миллисекунды, а подсчитать факториал большего числа уже проблематично, ведь разрядность целочисленных переменных в компиляторах имеет свои ограничения (например, переменная типа ulong является беззнаковым целым от 0 до 18446744073709551615).
    Тем не менее если включить фантазию и представить себя студентом, который должен решить три перечисленные задачи в одном алгоритме, то возможны любопытные варианты.
    Так, талантливый студент XX в. написал бы классический последовательный код, в общих чертах похожий на наше решение, приведенное ниже в листинге 1 (на языке C# :)). В этом решении из тела программы в строгой последовательности вызываются основные функции: Number (для нахождения максимального простого числа в определенном диапазоне от 1 до nNum), Fibonacci (для определения члена под номером nFib из ряда Фибоначчи) и Factorial (для вычисления факториала числа nFac), которые проводят соответствующие вычисления для целочисленных аргументов nNum, nFib, nFac. По умолчанию nNum = 200 000, nFib = 500 000 000, nFac = 65, но при желании в исполнительный процесс можно передать другие параметры с помощью строки приглашения (например, вот так: PCW_SingleThreadTest.exe 1000 100 10) - экспериментируйте.

    Изображение 1. Рабочий момент создания однопоточного кода в системе программирования Microsoft Visual C# 2005

    Кстати, в целях наглядности и компактности листинга мы не стали делать так называемую "защиту от идиотов", и поэтому передача в программу символьных переменных (или чисел с плавающей точкой) приведет к предсказуемой ошибке. К тому же не стоит забывать и о пределе размерности целочисленных типов.
    По пути отметим для пытливых читателей, что функция ToDefineTime является второстепенной в нашем алгоритме и предназначается лишь для наблюдения за "производительностью" кода (с ее помощью засекается время в миллисекундах, затраченное на выполнение ряда поставленных задач).
    Итак, после компиляции алгоритма из листинга 1 в системе программирования Microsoft Visual C# 2005 мы получим исполнительный файл PCW_SingleThreadTest.exe (название не так важно). И на двухъядерной платформе (Core 2 Duo E6700, Intel D975XBX, PC2-6400 2x512 Мбайт) эта программа выполняет заложенные вычисления за 1687 мс. Казалось бы, куда быстрее?
    Однако гипотетический студент XXI в. может запустить выполнение функций Number, Fibonacci и Factorial параллельно, слегка модифицировав листинг 1. Ведь современный студент знает, что программа на C# может представлять собой набор потоков, каждый из которых выступает объектом класса System.Threading.Thread.
    При этом в пространстве имен System.Threading важно выделить два метода, позволяющие запускать независимые фрагменты одного алгоритма в отдельных потоках: когда в вычислительную нить передается аргумент и когда в этом нет необходимости. В нашем случае мы передаем потокам thread1, thread2 и thread3 соответствующие переменные nNum, nFib и nFac, для чего используется делегат типа System.Threading.ParameterizedThreadStart (см. листинг 2). Если же метод в рамках потока будет иметь тип результата void (т.е. отсутствие типа) с пустым списком параметров, тогда создается делегат типа System.Threading.ThreadStart.
    Таким образом, основной кусочек листинга 1 (однопоточная версия) с последовательным вызовом трех функций:

    Number(nNum);
    Fibonacci(nFib);
    Factorial(nFac);

    можно трансформировать в соответствующий фрагмент листинга 2 (трехпоточная версия):

    Thread thread1 = new Thread(new ParameterizedThreadStart(Number));
    thread1.Start(nNum);
    Thread thread2 = new Thread(new ParameterizedThreadStart(Fibonacci));
    thread2.Start(nFib);
    Thread thread3 = new Thread(new ParameterizedThreadStart(Factorial));
    thread3.Start(nFac);
    thread1.Join();
    thread2.Join();
    thread3.Join();

    Здесь метод Start запускает отдельную нить вычислений и передает в нее соответствующую переменную, а метод Join ожидает реального завершения указанного потока. Кстати, если бы ставилась гипотетическая задача передать результат вычисления функции Number в функцию Fibonacci в качестве аргумента, то перед запуском нити thread2 возникла бы необходимость дождаться завершения выполнения потока thread1 методом thread1.Join(), а уж затем запускать thread2.
    Следует заметить, что метод Thread.Join является перегруженным, и факультативная переменная типа Int32 задавала бы время ожидания в миллисекундах. Так, метод thread3.Join(5000) ждал бы завершения потока в течение 5 с, после чего можно было бы форсировать завершение вычислительной нити thread3 методом thread3.Abort(), не дожидаясь вывода результатов.
    Но не будем в рамках статьи стараться поведать обо всех возможностях мультипрограммирования. Тем более что в языке C# отдельный поток может находиться в одном из следующих состояний (определяемом свойством Thread.ThreadState): незапущенный (Unstarted), исполнение (Running), ожидание (WaitSleepJoin), приостановленный (Suspended), прерванный (Aborted), завершенный (Stopped), - каждое из которых характеризуется своими методами, и детальную информацию о них (и не только) следует искать в удобной системе помощи Microsoft Visual Studio 2005.
    Мы же вернемся к компиляции листинга 2, в результате которой получается файл PCW_MultiThreadTest.exe (название не так важно). И если запустить эту программу на двухъядерной платформе (Core 2 Duo E6700, Intel D975XBX, PC2-6400 2x512 Мбайт), то становится очевидным выигрыш от многопоточной реализации нашего алгоритма - 1031 мс вместо 1687.

    Изображение 2. Результаты выполнения однопоточного кода на платформе с двухъядерным процессором Intel Core 2 Duo E6700

    Взглянув на экран, где выводятся результаты программы, можно догадаться, что быстрее всего со своей задачей справляется функция Fibonacci, а самым ресурсоемким фрагментом алгоритма является решето Эратосфена. Причем за время работы решета (thread1) без видимых сложностей успевают запуститься и увенчаться успехом потоки 2 и 3.
    Таким образом, потратив дополнительное время на небольшую модернизацию классического последовательного алгоритма, можно значительно увеличить эффективность его исполнения. И не стоит думать, что наши выводы далеки от практики. Например, в алгоритме работы востребованного архиватора (либо другой вариант - антивируса) можно организовать отдельные вычислительные потоки для каждого файла из выбранной для архивации (проверки на вирусы) папки. Если же пользователь пожелает сжать один большой файл, то можно разбить его на части и затем все их подвергнуть архивации в параллельных потоках. Разумеется, при разном количестве отдельных нитей будет меняться степень сжатия упомянутого файла, но в большинстве случаев можно будет достичь и высокой скорости выполнения задачи, и нужного уменьшения первоначального объема.
    Однако в процессе эффективной реализации технологий мультипрограммирования огорчают два момента. Во-первых, разработка сложного программного обеспечения подразумевает высокотехнологичные решения вопросов согласования работы вычислительных нитей и корректной передачи данных из одного потока в другой (например, с помощью методов класса System.Threading.Monitor). А во-вторых, распараллеленный код программного приложения скорее всего приведет к падению производительности решения на устаревших компьютерах с одноядерными процессорами.
    Давайте изучим таблицу результатов запуска нашего алгоритма на разных платформах - налицо регресс продуктивности многопоточной версии в отдельных конфигурациях трехлетней давности. А значит, в тексте идеальной программы потребуется еще и обращение к классам WMI (Windows Management Instrumentation - инструментарий управления ОС Windows) в пространстве имен System.Management, чтобы определить количество логических процессоров в системе и на основании их числа применить тот или иной способ решения поставленных задач.
    Например, вот этим кусочком кода можно определить число ЦП (переменная i):


    WqlObjectQuery queryCPU = new WqlObjectQuery("Select * from Win32_Processor");
    ManagementObjectSearcher findCPU = new ManagementObjectSearcher(queryCPU);
    foreach (ManagementObject mo in findCPU.Get())
    {
    ++i;
    }

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

    Таблица 1. Результаты выполнения компиляций
    Характеристики стенда Решение трех задач в алгоритме, мс *
    Конфигурация платформы Число
    ядер/потоков
    однопоточном многопоточном
    Intel Core 2 Duo E6700, Intel D975XBX, PC2-6400 1024 Мб 2/2 1687 1031
    Intel Core 2 Quad Q6600, Intel D975XBX, PC2-6400 1024 Мб 4/4 1860 1125
    Intel Pentium 4 3 ГГц HT, Intel i875P, PC-3200 1024 Мб 1/2 3532 3375
    Intel Pentium 4 3 ГГц, Intel i875P, PC-3200 1024 Мб 1/1 3531 3578
    AMD Athlon 64 3200+, VIA K8T800, PC-3200 256 Мб 1/1 59 015 61 125
    AMD Athlon XP 2500+, SIS 746FX, PC-2700 512 Мб 1/1 64 764 73 736
    * - Чем ниже показатели в миллисекундах, тем лучше

    Далеко ходить не надо

    Внимательные читатели отдельных компьютерных журналов, продаваемых вместе с CD-дисками, могли заметить, что отображение содержания носителя очень быстро появляется на экране, и пользователь может сразу приступать к работе. Однако по индикаторам работы жесткого диска можно догадаться, что программная оболочка не перешла целиком и полностью в режим ожидания ввода команд читателя, а выполняет какую-то работу в параллельном режиме.
    В частности, некоторые оболочки соответствующих CD-дисков разрабатываются компанией "Стокона" ( www.stocona.ru ) и вот какой информацией с нами поделился один из разработчиков упомянутой системы Богдан Гаркушин:
    "Проблема, с которой столкнулись разработчики компании "Стокона", - это обеспечение быстрой загрузки содержания журнала и быстрого поиска информации. Поскольку процесс подготовки поиска является более длительным, то его целесообразнее выделять в отдельный поток и запускать параллельно с загрузкой содержания журнала. И это позволяет значительно сократить время ожидания основной информации.
    Таким образом, основной поток загружает статьи журнала и сразу предоставляет их пользователю для чтения. Тем временем вспомогательная нить выполняет подготовку данных для поиска: загружает словарные базы, тематические словари, а также кэширует нужные файлы. И только по окончании работы вспомогательного потока в основной нити появляется возможность выполнения всех поисковых функций.
    Кстати, для пользователя сигналом о полной загрузке всех служб, обычно, служит остановка вращения логотипа компании "Стокона" в правом верхнем углу типичного интерфейса, а не состояние индикаторов жесткого диска :.
    Обычно предварительная загрузка данных занимает около минуты. Поэтому если выполнять ее в основном потоке, то время отображения оболочки при запуске значительно увеличится. А ведь для отображения информации и навигации по файлам CD-диска достаточно загрузки программы Acrobat Reader и эта операция сама по себе должна выполняться очень быстро. И только когда пользователь начинает спокойно читать журнал, оболочка инициирует довольно трудоемкую операцию загрузки вспомогательных данных в оперативную память. Так что не каждый читатель заметит нужную работу, выполняемую вторым потоком".

    Позвольте напомнить

    Решето Эратосфена - метод, разработанный Эратосфеном и позволяющий отсеивать составные числа из натурального ряда. Сущность его заключается в следующем.
    Зачеркивается единица. Число 2 - простое. Зачеркиваются все натуральные числа, делящиеся на 2. Число 3 - первое незачеркнутое число - будет простым. Далее зачеркиваем все натуральные числа, которые делятся на 3. Число 5 - следующее незачеркнутое число - будет простым. И так можно продолжать до бесконечности.

    Числа Фибоначчи - это элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13... , в которой каждый последующий член равен сумме двух предыдущих, а сама эта последовательность называется рядом Фибоначчи. Таким образом, число Фибоначчи можно вычислить по формуле Fibonacci(n) = Fibonacci(n-2) + Fibonacci(n-1). Например, 7-е число из ряда Фибоначчи соответствует Fibonacci(7) = Fibonacci(5) + Fibonacci(6) = 5 + 8 = 13.

    Факториал - это произведение натуральных чисел от единицы до какого-либо данного натурального числа n (т. е. 1*2*3*...*n), обозначается "n!". Например, 7! = 1*2*3*4*5*6*7 = 5040.

    Листинг 1. Выполнение трех вычислительных задач в одном потоке

    using System;
    namespace PCW_ThreadTest
    {
        class Program
        {
            static void Main(string[] args)
            {
                string sNum = ""; // строка из символов Unicode
                string sFib = "";
                string sFac = "";
                uint nNum = 0; // целое, беззнаковое, 32 бит
                uint nFib = 0;
                uint nFac = 0;
                int TimeIs = 0; // целочисленная переменная
                int nStartD = 0;
                int nFinishD = 0;
    
                // Если в программу не передаются аргументы, то по умолчанию - sNum = "200000"; sFib="500000000"; sFac = "65"
                if (args.Length < 3) { sNum = "200000"; sFib = "150000000"; sFac = "65"; }
                else { sNum = args[0]; sFib = args[1]; sFac = args[2]; }
                Console.WriteLine();
                Console.WriteLine("Программа получила число " + sNum + " в качестве аргумента для функции Number");
                Console.WriteLine("Программа получила число " + sFib + " в качестве аргумента для функции Fibonacci");
                Console.WriteLine("Программа получила число " + sFac + " в качестве аргумента для функции Factorial");
                Console.WriteLine();
    
                // Конвертируем переменные string в uint
                nNum = Convert.ToUInt32(sNum);
                nFib = Convert.ToUInt32(sFib);
                nFac = Convert.ToUInt32(sFac);
    
                ToDefineTime(ref TimeIs);
                nStartD = TimeIs;
    
                // /Вызываем 3 основные функции и выводим соответствующие результаты вычислений
                Number(nNum);
                Fibonacci(nFib);
                Factorial(nFac);
    
                TimeIs = 0;
                ToDefineTime(ref TimeIs);
                nFinishD = TimeIs;
                Console.WriteLine();
                if (nFinishD >= nStartD) TimeIs = nFinishD - nStartD;
                else TimeIs = 3600000 + nFinishD - nStartD;
                Console.WriteLine("Время выполнения заданий составило " + TimeIs + " миллисекунд");
                Console.Read();
            }
    
            public static void Number(uint n)
            {
                uint[] NumArray = new uint[n];
                uint nCount = 0;
                NumArray[nCount] = 2;
                bool bNum = true;
                for (uint i = 3; i <= n; i++)
                {
                    for (uint j = 0; j < nCount; j++)
                    {
                        if (i % NumArray[j] == 0) { bNum = false; break; }
                    }
                    if (bNum == true) { nCount++; NumArray[nCount] = i; }
                    else bNum = true;
                }
                Console.WriteLine("Максимальным простым числом до " + n + " является число " + NumArray[nCount]);
                return;
            }
    
            public static void Fibonacci(uint n)
            {
                if (n < 3) { Console.WriteLine(n + "-й член ряда Фибоначчи равняется 1"); return; }
                else
                {
                    uint[] FibArray = new uint[n];
                    FibArray[0] = 1;
                    FibArray[1] = 1;
                    for (uint i = 2; i < n; i++)
                    {
                        FibArray[i] = FibArray[i - 2] + FibArray[i - 1];
                    }
                    Console.WriteLine(n + "-й член ряда Фибоначчи равняется " + FibArray[n - 1]);
                    return;
                }
            }
            
            public static void Factorial(uint n)
            {
                ulong nfac = 1;
                for (uint i = 1; i <= n; i++)
                {
                    nfac = nfac * i;
                }
                Console.WriteLine("Факториал числа " + n + " равняется " + nfac);
                return;
            }
    
            public static void ToDefineTime(ref int TimeIs)
            {
                DateTime dt = DateTime.Now; // Определяем точное время, чтобы потом подсчитать продолжительность теста
                int dt05 = dt.Minute;
                int dt06 = dt.Second;
                int dt07 = dt.Millisecond;
                TimeIs = dt07 + (dt06*1000) + (dt05 * 60000);
            }
        }
    }
    

    Листинг 2. Выполнение трех вычислительных задач в трех потоках

    using System;
    using System.Threading;
    namespace PCW_ThreadTest
    {
        class Program
        {
            static void Main(string[] args)
            {
                string sNum = ""; // строка из символов Unicode
                string sFib = "";
                string sFac = "";
                uint nNum = 0; // целое, беззнаковое, 32 бит
                uint nFib = 0;
                uint nFac = 0;
                int TimeIs = 0; // целочисленная переменная
                int nStartD = 0;
                int nFinishD = 0;
                // Если в программу не передаются аргументы, то по умолчанию - sNum = "200000"; sFib="500000000"; sFac = "65"
                if (args.Length < 3) { sNum = "200000"; sFib = "150000000"; sFac = "65"; }
                else { sNum = args[0]; sFib = args[1]; sFac = args[2]; }
                Console.WriteLine();
                Console.WriteLine("Программа получила число " + sNum + " в качестве аргумента для функции Number");
                Console.WriteLine("Программа получила число " + sFib + " в качестве аргумента для функции Fibonacci");
                Console.WriteLine("Программа получила число " + sFac + " в качестве аргумента для функции Factorial");
                Console.WriteLine();
                // Конвертируем переменные string в uint (но в случае с параметрами object для потоков это лишнее)
                nNum = Convert.ToUInt32(sNum);
                nFib = Convert.ToUInt32(sFib);
                nFac = Convert.ToUInt32(sFac);
                ToDefineTime(ref TimeIs);
                nStartD = TimeIs;
                
                // Вызываем 3 основные функции и выводим соответствующие результаты вычислений
                Thread thread1 = new Thread(new ParameterizedThreadStart(Number));
                thread1.Start(nNum);
                Thread thread2 = new Thread(new ParameterizedThreadStart(Fibonacci));
                thread2.Start(nFib);
                Thread thread3 = new Thread(new ParameterizedThreadStart(Factorial));
                thread3.Start(nFac);
                thread1.Join();
                thread2.Join();
                thread3.Join();
    
                TimeIs = 0;
                ToDefineTime(ref TimeIs);
                nFinishD = TimeIs;
                Console.WriteLine();
                if (nFinishD >= nStartD) TimeIs = nFinishD - nStartD;
                else TimeIs = 3600000 + nFinishD - nStartD;
                Console.WriteLine("Время выполнения заданий составило " + TimeIs + " миллисекунд");
                Console.Read();
            }
            public static void Number(object oNum)
            {
                uint n = Convert.ToUInt32(oNum);
                uint[] NumArray = new uint[n];
                uint nCount = 0;
                NumArray[nCount] = 2;
                bool bNum = true;
                for (uint i = 3; i <= n; i++)
                {
                    for (uint j = 0; j < nCount; j++)
                    {
                        if (i % NumArray[j] == 0) { bNum = false; break; }
                    }
                    if (bNum == true) { nCount++; NumArray[nCount] = i; }
                    else bNum = true;
                }
                Console.WriteLine("Максимальным простым числом до " + n + " является число " + NumArray[nCount]);
                return;
            }
            public static void Fibonacci(object oFib)
            {
                uint n = Convert.ToUInt32(oFib);
                if (n < 3) { Console.WriteLine(n + "-й член ряда Фибоначчи равняется 1"); return; }
                else
                {
                    uint[] FibArray = new uint[n];
                    FibArray[0] = 1;
                    FibArray[1] = 1;
                    for (uint i = 2; i < n; i++)
                    {
                        FibArray[i] = FibArray[i - 2] + FibArray[i - 1];
                    }
                    Console.WriteLine(n + "-й член ряда Фибоначчи равняется " + FibArray[n - 1]);
                    return;
                }
            }
            public static void Factorial(object oFac)
            {
                uint n = Convert.ToUInt32(oFac);
                ulong nfac = 1;
                for (uint i = 1; i <= n; i++)
                {
                    nfac = nfac * i;
                }
                Console.WriteLine("Факториал числа " + n + " равняется " + nfac);
                return;
            }
            public static void ToDefineTime(ref int TimeIs)
            {
                DateTime dt = DateTime.Now; // Определяем точное время, чтобы потом подсчитать продолжительность теста
                int dt05 = dt.Minute;
                int dt06 = dt.Second;
                int dt07 = dt.Millisecond;
                TimeIs = dt07 + (dt06*1000) + (dt05 * 60000);
            }
        }
    }
    

    >> НАВЕРХ СТРАНИЦЫ <<