Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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();
            }
        }
    }
}
share|improve this question
1  
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
add comment

1 Answer

up vote 1 down vote accepted

Assuming that the processes are completely independent (no resource contention), and each process has an infinite input queue, processing all the items will take about as long as it takes the slowest process to handle all the data, plus the time for the first item to reach the slowest process, plus the time to complete the last item after it leaves the slowest process.

share|improve this answer
    
I thought the same thing originally, but my numbers do not match what is happening. For example, the steps with execution times of {1,2,5,2,2,4,3} (measurement in ticks), my program says it takes 61 ticks to process. Your formula says it takes 64 ticks. –  Charles Lambert Dec 1 '11 at 22:47
3  
@CharlesLambert - I think you are looking for an impossible level of precision. –  John Buchanan Dec 1 '11 at 23:22
    
@CharlesLambert Your simulation program is wrong. In each tick, it advances the progress of all steps, even those that have no item to work on. –  JGWeissman Dec 2 '11 at 0:38
    
@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
1  
@Charles -- of course it is possible to compute this number. It cannot be done by formula, but it is certainly computable in O(i*p). –  kevin cline Dec 2 '11 at 17:10
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.