# Is there a formula to figure out the total execution time of sequential asynchronous processes?

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;
}
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");
}

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);
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);
}

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();
}
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();
}
}
}
}
``````
• You cannot solve this problem without knowing about your scheduler. How many concurrent threads can you run? How are they scheduled? Is there anything else running as well, that could affect your timing? Are you counting only the CPU time (the actual running time of the threads), or idle as well (the total time you need to run the program to get the final result)? – littleadv Dec 1 '11 at 22:19
• @littleadv - I understand those are valid things to take into consideration, but I left that stuff out because it is not important to the problem i'm trying to solve. You could say I'm assuming infinite threads, no time for thread switching, etc. – Charles Lambert Dec 1 '11 at 22:34

• @JGWeissman - if the number of items to be processed for a step are zero, the method just returns `if(Count == 0) return` – Charles Lambert Dec 2 '11 at 4:19