c # Многопоточность только с использованием 25% процессора

Question

У меня есть процесс для своего рода алгоритма генетического вложения, который я пытаюсь использовать в многопоточном режиме.Процесс выглядит примерно так:

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

namespace ConsoleApp1
{
  class Program
  {
    static void Main(string[] args)
    {
      CurrentNest = new CuttingRun();
      for (int i = 0; i < 80; i++)
      {
        double w = GetRandomNumber(24, 50);
        double h = GetRandomNumber(10, 15);
        CurrentNest.PartList.Add(new LwCube { Width = w, Height = h, PartID = i });
      }
      //Task.Run(() =>
      //{
      //  Parallel.For(0, 64, (i) => Parallel_Nest());
      //});
      while (true)
      {
        Parallel_Nest();
      }
      //Console.ReadKey();
    }

    public static double GetRandomNumber(double minimum, double maximum)
    {
      Random random = new Random();
      return random.NextDouble() * (maximum - minimum) + minimum;
    }

    public static CuttingRun CurrentNest { get; set; }
    public static void Parallel_Nest()
    {
      Random random = new Random();
      int randomNumber = random.Next(2000, 10000);     
      var retVal = Nester.Nest_Parts(CurrentNest, randomNumber);
      CurrentNest.Iterations++;
      if (CurrentNest.SavedList.Count > 0)
      {
        if (retVal.Count < CurrentNest.SavedList.Count)
        {
          CurrentNest.SavedList = retVal;          
        }
      }
      else
      {
        CurrentNest.SavedList = retVal;
      }
      Console.WriteLine(CurrentNest.Iterations.ToString() + " " + CurrentNest.SavedList.Count.ToString());
      if (CurrentNest.SavedList != retVal)
      {
        retVal.Clear();
      }
    }    
  }


//Models
public class LwSheet
  {
    public LwSheet(double width, double height)
    {
      SheetWidth = width;
      SheetHeight = height;
      FreeRectangles.Add(new LwCube { Width = width, Height = height, X = 0, Y = 0 });
    }
    public List<LwCube> UsedRectangles = new List<LwCube>();
    public List<LwCube> FreeRectangles = new List<LwCube>();
    public double SheetWidth { get; set; }
    public double SheetHeight { get; set; }
    public double TotalUsed { get; set; }
    public bool Place_Part(LwCube prt)
    {
      bool retVal = false;
      LwCube bestNode = FindPositionForBestAreaFit(prt);
      //if the bestNode has a height then add our parts to the list
      if (bestNode.Height > 0)
      {
        bestNode.PartID = prt.PartID;
        int numRectanglesToProcess = FreeRectangles.Count;
        for (int i = 0; i < numRectanglesToProcess; ++i)
        {
          if (SplitFreeNode(FreeRectangles[i], ref bestNode))
          {
            FreeRectangles.RemoveAt(i);
            --i;
            --numRectanglesToProcess;
          }
        }

        PruneFreeList();
        UsedRectangles.Add(bestNode);
        retVal = true;
      }
      return retVal;
    }
    bool SplitFreeNode(LwCube freeNode, ref LwCube usedNode)
    {
      // Test with SAT if the rectangles even intersect.
      if (usedNode.X >= freeNode.X + freeNode.Width || usedNode.X + usedNode.Width <= freeNode.X ||
        usedNode.Y >= freeNode.Y + freeNode.Height || usedNode.Y + usedNode.Height <= freeNode.Y)
        return false;

      if (usedNode.X < freeNode.X + freeNode.Width && usedNode.X + usedNode.Width > freeNode.X)
      {
        // New node at the top side of the used node.
        if (usedNode.Y > freeNode.Y && usedNode.Y < freeNode.Y + freeNode.Height)
        {
          LwCube newNode = new LwCube { Width = freeNode.Width, X = freeNode.X, Y = freeNode.Y };
          newNode.Height = usedNode.Y - newNode.Y;
          FreeRectangles.Add(newNode);
        }

        // New node at the bottom side of the used node.
        if (usedNode.Y + usedNode.Height < freeNode.Y + freeNode.Height)
        {
          LwCube newNode = new LwCube { Width = freeNode.Width, X = freeNode.X };
          newNode.Y = usedNode.Y + usedNode.Height;
          newNode.Height = freeNode.Y + freeNode.Height - (usedNode.Y + usedNode.Height);
          FreeRectangles.Add(newNode);
        }
      }

      if (usedNode.Y < freeNode.Y + freeNode.Height && usedNode.Y + usedNode.Height > freeNode.Y)
      {
        // New node at the left side of the used node.
        if (usedNode.X > freeNode.X && usedNode.X < freeNode.X + freeNode.Width)
        {
          LwCube newNode = new LwCube { Height = freeNode.Height, X = freeNode.X, Y = freeNode.Y };
          newNode.Width = usedNode.X - newNode.X;
          FreeRectangles.Add(newNode);
        }

        // New node at the right side of the used node.
        if (usedNode.X + usedNode.Width < freeNode.X + freeNode.Width)
        {
          LwCube newNode = new LwCube { Height = freeNode.Height, Y = freeNode.Y };
          newNode.X = usedNode.X + usedNode.Width;
          newNode.Width = freeNode.X + freeNode.Width - (usedNode.X + usedNode.Width);
          FreeRectangles.Add(newNode);
        }
      }

      return true;
    }    
    void PruneFreeList()
    {
      for (int i = 0; i < FreeRectangles.Count; ++i)
        for (int j = i + 1; j < FreeRectangles.Count; ++j)
        {
          if (IsContainedIn(FreeRectangles[i], FreeRectangles[j]))
          {
            FreeRectangles.RemoveAt(i);
            --i;
            break;
          }
          if (IsContainedIn(FreeRectangles[j], FreeRectangles[i]))
          {
            FreeRectangles.RemoveAt(j);
            --j;
          }
        }
    }
    bool IsContainedIn(LwCube a, LwCube b)
    {
      return a.X >= b.X && a.Y >= b.Y
        && a.X + a.Width <= b.X + b.Width
        && a.Y + a.Height <= b.Y + b.Height;
    }
    LwCube FindPositionForBestAreaFit(LwCube prt)
    {
      LwCube bestNode = new LwCube();
      var bestAreaFit = SheetWidth * SheetHeight;
      for (int i = 0; i < FreeRectangles.Count; ++i)
      {
        double areaFit = FreeRectangles[i].Width * FreeRectangles[i].Height - prt.Width * prt.Height;

        // Try to place the rectangle in upright (non-flipped) orientation.
        if (FreeRectangles[i].Width >= prt.Width && FreeRectangles[i].Height >= prt.Height)
        {
          if (areaFit < bestAreaFit)
          {
            bestNode.X = FreeRectangles[i].X;
            bestNode.Y = FreeRectangles[i].Y;
            bestNode.Height = prt.Height;
            bestNode.Width = prt.Width;
            bestAreaFit = areaFit;
          }
        }
      }
      return bestNode;
    }   
  }

  public class LwCube
  {
    public int PartID { get; set; }
    public double Width { get; set; }
    public double Height { get; set; }
    public double X { get; set; }
    public double Y { get; set; }
  }

  public class CuttingRun
  {    
    public List<LwCube> PartList = new List<LwCube>();
    public List<LwSheet> SavedList = new List<LwSheet>();
    public List<LwSheet> Sheets = new List<LwSheet>();
    public int Iterations { get; set; }
  }


//Actions
public static class Nester
  {
    public static List<LwSheet> Nest_Parts(CuttingRun cuttingRun, int loopCount)
    {
      var SheetList = new List<LwSheet>();
      List<LwCube> partList = new List<LwCube>();
      partList.AddRange(cuttingRun.PartList);
      while (partList.Count > 0)
      {
        LwSheet newScore = new LwSheet(97, 49);
        List<LwCube> addingParts = new List<LwCube>();
        foreach (var prt in partList)
        {
          addingParts.Add(new LwCube { Width = prt.Width, Height = prt.Height, PartID = prt.PartID });
        }
        if (addingParts.Count > 0)
        {
          var sheets = new ConcurrentBag<LwSheet>();
          Parallel.For(0, loopCount, (i) =>
          {
            var hmr = new LwSheet(97, 49);
            Add_Parts_To_Sheet(hmr, addingParts);
            sheets.Add(hmr);
          });
          //for (int i = 0; i < loopCount; i++)
          //{
          //  var hmr = new LwSheet(97, 49);

          //  Add_Parts_To_Sheet(hmr, addingParts, addToLarge, addToMedium);
          //  sheets.Add(hmr);
          //}
          addingParts.Clear();
          var bestSheet = sheets.Where(p => p != null).OrderByDescending(p => p.TotalUsed).First();
          sheets = null;
          newScore = bestSheet;
          foreach (var ur in newScore.UsedRectangles)
          {
            partList.Remove(partList.Single(p => p.PartID == ur.PartID));
          }
          SheetList.Add(newScore);
        }
      }
      return SheetList;
    }       
    public static void Add_Parts_To_Sheet(LwSheet sh, List<LwCube> parts)
    {
      var myList = new List<LwCube>();
      myList.AddRange(parts);
      myList.Shuffle();
      foreach (var prt in myList)
      {
        sh.Place_Part(prt);
      }
      myList.Clear();
      foreach (var ur in sh.UsedRectangles)
      {
        sh.TotalUsed += ur.Width * ur.Height;
      }
    }

    [ThreadStatic] private static Random Local;
    public static Random ThisThreadsRandom
    {
      get { return Local ?? (Local = new Random(unchecked(Environment.TickCount * 31 + System.Threading.Thread.CurrentThread.ManagedThreadId))); }
    }

    public static void Shuffle<T>(this IList<T> list)
    {
      int n = list.Count;
      while (n > 1)
      {
        n--;
        int k = ThisThreadsRandom.Next(n + 1);
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
      }
    }
  }
}

Я попытался использовать параллельные циклы for для каждого из циклов, чтобы попытаться ускорить процесс.Я также попытался изменить их на задачи и использовал задачу. Когда все.Однако я могу использовать только около 25% своего процессора.Если я запускаю программу 4 раза, я могу использовать 100%.Мне интересно, есть ли у кого-нибудь идеи о том, как я мог бы использовать 100% своего процессора, не запуская программу более одного раза?РЕДАКТИРОВАТЬ: После добавления уменьшенной рабочей версии я также закомментировал один из параллельных циклов и один из нормальных циклов, чтобы показать, куда я поместил их в код.

Answer 1

Однако я могу использовать только около 25% своего процессора.Если я запускаю программу 4 раза, я могу использовать 100%.Мне интересно, есть ли у кого-нибудь идеи о том, как я мог бы использовать 100% своего ЦП без повторного запуска программы?

Ваш код представляет собой смесь асинхронного (предположительно, ввода-выводасвязанные) и параллельные (предположительно связанные с процессором) части.Я говорю «кажется», потому что мы не можем точно сказать, в чем проблема, поскольку это не минимальный воспроизводимый пример .

Но, если это предположение верно, тоПричина, по которой ваш ЦП используется недостаточно, проста: параллельные части, связанные с ЦП, ожидают своих входных данных от асинхронных частей, связанных с вводом / выводом.Единственный способ исправить это - запустить части, связанные с вводом / выводом, одновременно.Переместите свой связанный с вводом / выводом код как можно раньше в конвейер, а затем убедитесь, что участки, связанные с вводом / выводом, выполняются как можно более параллельно.Например, если вам нужно вызвать WebApi для каждого элемента, позвоните ему, как только у вас есть элемент;или если вы читаете элементы из базы данных, попробуйте прочитать как можно больше в пакете.Это позволяет минимизировать количество времени, в течение которого части, связанные с процессором, должны ждать своих данных.

«Асинхронный параллельный ForEach» редко является хорошим инструментом для решения подобных проблем.Я бы либо посмотрел на поток данных TPL, либо построил бы свой собственный конвейер, используя каналы.

В конце концов, вполне возможно, что алгоритм в целом связан с вводом / выводом.В этом случае не так уж много вы можете сделать: будет использоваться только один ЦП, потому что ввод-вывод не может идти в ногу с этим единственным ЦП, и в этом случае использование большего количества ЦП не даст никакой выгоды.