Pipeline Stages and Processing Models

Introduction

  • The discussion revolves around processing toy orders using two different concurrency models: the boss-worker model and the pipeline model.

Boss-Worker Model

  • Total Toy Orders: 10 orders

  • Threads: 6 total, consisting of:

    • 1 Boss thread

    • 5 Worker threads

  • Processing Capability:

    • With 5 workers, the system can process up to 5 toy orders simultaneously.

    • Time Calculation for 10 Toy Orders:

    • First 5 Orders: Each of the 5 workers takes 120 milliseconds to process.

      • Total time for first 5 orders: 120 milliseconds.

    • Next 5 Orders: These will also take an additional 120 milliseconds.

      • Total time for second batch: 120 milliseconds.

  • Cumulative Processing Time:

    • First 5 orders + Next 5 orders = 120 ms + 120 ms = 240 milliseconds.

Pipeline Model

  • Total Toy Orders: 10 orders

  • Threads: 6 total, each performing one stage of processing.

  • Time Calculation for 10 Toy Orders:

    • First Toy Order: Takes 120 milliseconds to pass through all six stages of the pipeline (6 stages x 20 milliseconds/stage).

    • Remaining 9 Toy Orders: Each takes 20 milliseconds to complete once the previous order has exited the pipeline.

      • Calculation: 120 ms + (9 orders x 20 ms) = 120 ms + 180 ms = 300 milliseconds.

Case with 11 Toy Orders

  • Boss-Worker Model:

    • Total toy orders increase from 10 to 11.

    • First 10 Orders: Processed in the same manner as before; total time remains 240 milliseconds.

    • 11th Order: One worker will process this order alone, which takes an additional 120 milliseconds.

    • Cumulative Processing Time:

    • For 10 orders + 11th order = 240 ms + 120 ms = 360 milliseconds.

  • Pipeline Model:

    • First Toy Order: Remains at 120 milliseconds for the initial order.

    • Remaining 10 Toy Orders: Each takes 20 milliseconds to finish processing.

    • Calculation: 120 ms + (10 orders x 20 ms) = 120 ms + 200 ms = 320 milliseconds.

Comparative Analysis of Models

  • For 10 Toy Orders:

    • Boss-Worker Model Total Time: 240 milliseconds.

    • Pipeline Model Total Time: 300 milliseconds.

    • Conclusion: Boss-Worker is more efficient with 10 orders.

  • For 11 Toy Orders:

    • Boss-Worker Model Total Time: 360 milliseconds.

    • Pipeline Model Total Time: 320 milliseconds.

    • Conclusion: Pipeline is more efficient with 11 orders.

Conclusion

  • Finding the Better Model:

    • The effectiveness of a model depends on input size:

    • For 10 orders, the Boss-Worker model works better.

    • For 11 orders, the Pipeline model is better.

  • Consideration for Real-World Applications:

    • Execution time calculations are simplified in this discussion.

    • In practice, overheads due to synchronization and data passing among threads through shared memory queues must be taken into account.

    • A more complex experimental analysis is necessary to accurately assess the better pattern for various applications.