Как планировать работы без наложения с использованием LINQ to Objects? - PullRequest
Новая
       9

Как планировать работы без наложения с использованием LINQ to Objects?

2 голосов
/ 17 марта 2011

Это еще одна проблема выделения ресурсов. Моя цель - запустить запрос, чтобы назначить приоритетное задание для любого временного интервала одному из двух ядер ЦП (просто пример, поэтому давайте не будем прерывать или выполнять многозадачность). Примечание: это похоже на мой предыдущий пост о разбиении , но фокусируется на перекрывающихся временах и назначении нескольких элементов, а не только самого приоритетного элемента.

Вот наш объект: 

public class Job
{
    public int Id;
    public int Priority;
    public DateTime Begin;
    public DateTime End;
}

Реальный набор данных очень большой, но для этого примера, скажем, есть 1000 заданий, которые можно назначить двум ядрам ЦП. Все они загружены в память, и мне нужно выполнить один запрос LINQ to Objects к ним. В настоящее время это занимает почти 8 секунд и 1,4 миллиона сравнений.

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

Прежде чем я доберусь до кода, позвольте мне указать этапы текущего неэффективного алгоритма:

  1. Определить оставшиеся задания (удалив все уже назначенные)
  2. Назначение заданий текущему ядру путем самостоятельного объединения всех оставшихся заданий и выбора верхнего перекрывающегося задания по приоритету.
  3. Объединить новые задания, выполнив запрос
  4. Повторите, начиная с остановки 1 для каждого оставшегося ядра

Вопросы:

  • Как это можно сделать наиболее эффективно?
  • Можно ли избежать подзапроса на шаге 2? Возможно группировкой, но я не уверен, как я могу группировать на основе метода расширения .Overlaps ().
  • Работы уже заказаны. Может ли шаг 2 использовать тот факт, который сравнивается только с предметами, находящимися на близком расстоянии, а не с каждой работой?
  • Есть ли более эффективные назначения для ядер, нежели зацикливание? Это может избежать выполнения запроса на шаге 3? Опять же, если бы я мог группировать наборы перекрывающихся заданий, то назначение ядер - это просто вопрос выбора N для перекрывающегося набора.

Полный образец кода: 

public class Job
{
    public static long Iterations;

    public int Id;
    public int Priority;
    public DateTime Begin;
    public DateTime End;

    public bool Overlaps(Job other)
    {
        Iterations++;
        return this.End > other.Begin && this.Begin < other.End;
    }
}

public class Assignment
{
    public Job Job;
    public int Core;
}

class Program
{
    static void Main(string[] args)
    {
        const int Jobs = 1000;
        const int Cores = 2;
        const int ConcurrentJobs = Cores + 1;
        const int Priorities = Cores + 3;
        DateTime startTime = new DateTime(2011, 3, 1, 0, 0, 0, 0);
        Console.WriteLine(string.Format("{0} Jobs x {1} Cores", Jobs, Cores));
        var timer = Stopwatch.StartNew();

        Console.WriteLine("Populating data");
        var jobs = new List<Job>();
        for (int jobId = 0; jobId < Jobs; jobId++)
        {
            var jobStart = startTime.AddHours(jobId / ConcurrentJobs).AddMinutes(jobId % ConcurrentJobs);
            jobs.Add(new Job() { Id = jobId, Priority = jobId % Priorities, Begin = jobStart, End = jobStart.AddHours(0.5) });
        }
        Console.WriteLine(string.Format("Completed in {0:n}ms", timer.ElapsedMilliseconds));
        timer.Restart();

        Console.WriteLine("Assigning Jobs to Cores");
        IEnumerable<Assignment> assignments = null;
        for (int core = 0; core < Cores; core++)
        {
            // avoid modified closures by creating local variables
            int localCore = core;
            var localAssignments = assignments;

            // Step 1: Determine the remaining jobs
            var remainingJobs = localAssignments == null ? 
                                                jobs :
                                                from j in jobs where !(from a in localAssignments select a.Job).Contains(j) select j;

            // Step 2: Assign the top priority job in any time-slot to the core
            var assignmentsForCore = from s1 in remainingJobs
                              where
                                  (from s2 in remainingJobs
                                   where s1.Overlaps(s2)
                                   orderby s2.Priority
                                   select s2).First().Equals(s1)
                              select new Assignment { Job = s1, Core = localCore };

            // Step 3: Accumulate the results (unfortunately requires a .ToList() to avoid massive over-joins)
            assignments = assignments == null ? assignmentsForCore.ToList() : assignments.Concat(assignmentsForCore.ToList());
        }

        // This is where I'd like to Execute the query one single time across all cores, but have to do intermediate steps to avoid massive-over-joins
        assignments = assignments.ToList();

        Console.WriteLine(string.Format("Completed in {0:n}ms", timer.ElapsedMilliseconds));
        Console.WriteLine("\nJobs:");
        foreach (var job in jobs.Take(20))
        {
            Console.WriteLine(string.Format("{0}-{1} Id {2} P{3}", job.Begin, job.End, job.Id, job.Priority));
        }

        Console.WriteLine("\nAssignments:");
        foreach (var assignment in assignments.OrderBy(a => a.Job.Begin).Take(10))
        {
            Console.WriteLine(string.Format("{0}-{1} Id {2} P{3} C{4}", assignment.Job.Begin, assignment.Job.End, assignment.Job.Id, assignment.Job.Priority, assignment.Core));
        }

        Console.WriteLine(string.Format("\nTotal Comparisons: {0:n}", Job.Iterations));

        Console.WriteLine("Any key to continue");
        Console.ReadKey();
    }
}

Пример вывода:

1000 заданий x 2 ядра
Заполнение данных
Завершено за 0,00 мс
Назначение заданий ядрам
Завершено за 7 998,00 мс

Работа:
01.03.2011 12:00:00-03/1/2011 12:30:00 AM Id 0 P0
01.03.2011, 00:01, 01.03.2011, 00:31, Id 1 P1
01.03.2011 12:02:00-03/01/2011 0:32:00 Id 2 P2
01.03.2011 1:00:00 AM-3/1/2011 1:30:00 AM Id 3 P3
01.03.2011 1:01:00 AM-3/1/2011 1:31:00 AM Id 4 P4
01.03.2011 1:02:00 AM-1/2011 1:32:00 AM Id 5 P0
01.03.2011 2:00:00 AM-3/1/2011 2:30:00 AM Id 6 P1
01.03.2011 2:01:00 AM-1/2011 / 2:31:00 AM Id 7 P2
01.03.2011 2:02:00 AM-1/2011 / 2:32:00 AM Id 8 P3
01.03.2011 3:00:00 AM-1/2011 3:30:00 AM Id 9 P4
01.03.2011 3:01:00 AM-1/2011 / 3:31:00 AM Id 10 P0
01.03.2011 3:02:00 AM-1/2011 / 3:32:00 AM Id 11 P1
01.03.2011 4:00:00 AM-3/1/2011 4:30:00 AM Id 12 P2
01.03.2011 4:01:00 AM-1/2011 / 4:31:00 AM Id 13 P3
01.03.2011 4:02:00 AM-1/2011 4:32:00 AM Id 14 P4
01.03.2011 5:00:00 AM-3/1/2011 5:30:00 AM Id 15 P0
01.03.2011 5:01:00 AM-1/2011 / 5:31:00 AM Id 16 P1
01.03.2011 5:02:00 AM-1/2011 5:32:00 AM Id 17 P2
01.03.2011 6:00:00 AM-3/1/2011 6:30:00 AM Id 18 P3
01.03.2011 6:01:00 AM-1/2011 / 6:31:00 AM Id 19 P4

Назначение:
01.03.2011 12:00:00 AM-1/2011 12:30:00 AM Id 0 P0 C0
01.03.2011, 00:01, 01.03.2011, 00:31, Id 1 P1 C1
01.03.2011 1:00:00 AM-3/1/2011 1:30:00 AM Id 3 P3 C1
01.03.2011 1:02:00 AM-01/2011 1:32:00 AM Id 5 P0 C0
01.03.2011 2:00:00 AM-3/1/2011 2:30:00 AM Id 6 P1 C0
01.03.2011 2:01:00 AM-3/1/2011 2:31:00 AM Id 7 P2 C1
01.03.2011 3:01:00 AM-1/2011 / 3:31:00 AM Id 10 P0 C0
01.03.2011 3:02:00 AM-1/2011 / 3:32:00 AM Id 11 P1 C1
01.03.2011 4:00:00 AM-3/1/2011 4:30:00 AM Id 12 P2 C0
01.03.2011 4:01:00 AM-1/2011 / 4:31:00 AM Id 13 P3 C1
01.03.2011 5:00:00 AM-3/1/2011 5:30:00 AM Id 15 P0 C0

Всего сравнений: 1 443 556,00
Любая клавиша для продолжения

Ответы [ 2 ]

1 голос
/ 17 марта 2011

Есть ли причина для использования linq для сбора объектов для этой задачи? Я думаю, что я бы создал активный список, поместил бы все задания в очередь и вытолкнул следующее из очереди, когда активный список опустился ниже 10, и вставил бы его в активный список. Достаточно легко отследить, какое ядро ​​выполняет какую задачу, и назначить следующую задачу в очереди наименее загруженному ядру. Подключите законченное событие к заданию или просто просмотрите активный список, и вы узнаете, когда уместно добавить другое задание из очереди в активный список.

0 голосов
/ 17 марта 2011

Я бы предпочел сделать это за один цикл.Мой результат отличается от вашего.У вас запланировано 2/3 всех заданий.Шахта запланирована всем.Я добавлю объяснения позже.Уходить на встречу сейчасПереработка на это ..: P

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

Похожие темы

...