I have a set of steps that need to run sequentially over a list of data. However each step only operates on a single piece of data at a time. Because of this, I can run the steps asynchronously.
For example I have two pieces of data, and two steps. When step one is done processing the first piece of data, it passes it to step two. Now step one processes the second piece of data while step two is processing the first piece of data. So forth and so on until all of the data has been processed by each step.
In contrast, looping through the list of items and executing every sequentially in order turns into the equation:
total_time = (step1 + step2 + ... + stepN) * number_of_items
Given that I know the execution time of each step for a single piece of data, and I know the number of items to be processed, is there a formula that will tell me the total execution time for processing all the data items asynchronously?
I have written a program (see below) that simulates this process. I'm not entirely sure that it is computing it correctly, but I believe it is close. This was my attempt at figuring out how to solve the problem. I'm including it here to show my understanding of the problem, which may be wrong.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace ConsoleApplication1 {
class Step : Queue<object> {
public Step(int totalExecutionTime)
{
_totalExecutionTime = totalExecutionTime;
CurrentExecutionTime = _totalExecutionTime;
}
readonly int _totalExecutionTime;
public Queue<object> NextStep { private get; set; }
public int CurrentExecutionTime { get; private set; }
public void RunTick()
{
if (Count == 0)
return;
if (CurrentExecutionTime == 0)
CurrentExecutionTime = _totalExecutionTime;
CurrentExecutionTime--;
if (CurrentExecutionTime == 0 && NextStep != null)
NextStep.Enqueue(Dequeue());
}
}
class Program {
static void Main(string[] args)
{
int totalItems = 10;
int[] stepLengths = new int[] { 1,2,5,2,2 };
if (File.Exists("output.txt"))
File.Delete("output.txt");
WriteLine("ASYNC: {0}", TotalTime(totalItems, stepLengths));
WriteLine("SEQUENTIAL: {0}", stepLengths.Sum() * totalItems);
Console.WriteLine("DONE");
Console.ReadLine();
}
static int TotalTime2(int totalItems, int[] stepLengths)
{
throw new NotImplementedException();
}
private static int TotalTime(int totalItems, int[] stepLengths)
{
var steps = new List<Step>();
Step prevStep = null;
foreach(var stepLength in stepLengths) {
var step = new Step(stepLength);
steps.Add(step);
if (prevStep != null)
prevStep.NextStep = step;
prevStep = step;
}
var first = steps.First();
for(int i = 0; i < totalItems; i++) {
first.Enqueue(new object());
}
var last = steps.Last();
var revSteps = steps.Reverse<Step>().ToList();
var totalTime = 0;
do
{
Display(steps, totalTime);
revSteps.ForEach(s => s.RunTick());
totalTime++;
} while (last.Count < totalItems);
if (last.CurrentExecutionTime > 0)
{
do
{
Display(steps, totalTime);
revSteps.ForEach(s => s.RunTick());
totalTime++;
} while (last.CurrentExecutionTime > 0);
}
Display(steps, totalTime);
return totalTime;
}
static void Display(List<Step> steps, int totalTime)
{
Write("[");
steps.ForEach(s => Write("{0},", s.CurrentExecutionTime.ToString().PadLeft(2)));
WriteLine("]");
Write("[");
steps.ForEach(s => Write("{0},", s.Count.ToString().PadLeft(2)));
WriteLine("] {0}", totalTime.ToString().PadLeft(5));
WriteLine();
}
static void Write(string fmt, params object[] args)
{
Console.Write(fmt, args);
using (var w = new StreamWriter("output.txt", true))
{
w.Write(fmt, args);
}
}
static void WriteLine(string fmt, params object[] args)
{
Console.WriteLine(fmt, args);
using (var w = new StreamWriter("output.txt", true))
{
w.WriteLine(fmt, args);
}
}
static void WriteLine()
{
Console.WriteLine();
using (var w = new StreamWriter("output.txt", true))
{
w.WriteLine();
}
}
}
}
