4 ms·

I'm guessing https://en.wikipedia.org/wiki/Donald_B._Gillies https://en.wikipedia.org/wiki/Donald_B._Gillies is a good bet for this claim.

adrian_b 2y ago
Nope. 1957 in a transistorized computer is far too late for the origin of pipelining. Pipelining had already been used in computers with vacuum tubes a few years before and it had also been used already a decade earlier in computers with electromechanical relays, i.e. IBM SSEC, which had a 3-stage pipeline for the execution of its instructions (IBM SSEC had a Harvard architecture, with distinct kinds of memories for program and for data). Before 1959, pipelining was named "overlapped execution". The first use of the word "pipeline" was as a metaphor in the description of the IBM Stretch computer, in 1959. The word "pipeline" began to be used as a verb, with forms like "pipelining" and "pipelined" around 1965. The first paper where I have seen such a verbal use was from the US Army. Outside computing, pipelining as a method of accelerating iterative processes had been used for centuries in the progressive assembly lines, e.g. for cars, and before that for ships or engines. Pipelined execution and parallel execution are dual methods for accelerating an iterative process that transforms a stream of data. In the former the process is divided into subprocesses through which the stream of data passes in series, while in the latter the stream of data is divided into substreams that go in parallel through multiple instances of the process.
- cogman10 2y ago
  The earliest "pipeline" example I can find is the portsmouth block mills [1] implemented by Marc Brunel[2]/Henry Maudslay[3] around 1802 [1] https://en.wikipedia.org/wiki/Portsmouth_Block_Mills https://en.wikipedia.org/wiki/Portsmouth_Block_Mills [2] https://en.wikipedia.org/wiki/Marc_Isambard_Brunel https://en.wikipedia.org/wiki/Marc_Isambard_Brunel [3] https://en.wikipedia.org/wiki/Henry_Maudslay https://en.wikipedia.org/wiki/Henry_Maudslay
  - bjourne 2y ago
    Before that you had bucket brigades.
  - adrian_b 2y ago
    Wikipedia gives another much more ancient example of a "pipeline", the Venetian Arsenal, which had a progressive assembly line for ships, which had a throughput that could be greater than of one ship per day, and which has been built in the 12th century.
- formerly_proven 2y ago
  Zuse Z3 had a three stage instruction pipeline.
  - adrian_b 2y ago
    If this is true, then it resembles in this feature the IBM SSEC, another electromechanical computer with a three stage instruction pipeline, which however was built only later, after WWII, between 1944 and 1947. The main inspiration for IBM SSEC has been Harvard Mark I, an earlier electromechanical computer built by IBM based on a design done mostly by Howard Aiken, but it would not have been impossible for some information about the Zuse computers to have reached IBM after WWII, contributing to the design of the SSEC.
- Voultapher 2y ago
  > Pipelined execution and parallel execution are dual methods for accelerating an iterative process that transforms a stream of data. In the former the process is divided into subprocesses through which the stream of data passes in series, while in the latter the stream of data is divided into substreams that go in parallel through multiple instances of the process. With parallel do you mean superscalar execution i.e. having two ALUs or do you mean having multiple cores?
  - adrian_b 2y ago
    Parallel execution can exist at many different levels, e.g. at processor level you can have multiple processors executing in parallel some threads. At instruction level, the execution of instructions is an iterative process, so like for any other iterative process parallelism or pipelining or both parallelism and pipelining may be used. Most modern CPUs use both parallelism and pipelining in the execution of instructions. If you have e.g. a stream of multiply instructions, the CPU may have for example 2 multiply pipelines, where each multiply pipeline has 4 stages. The incoming multiply instruction stream is divided into 2 substreams, which are dispatched in parallel to the 2 multiply pipelines, so 2 multiply instructions are initiated in each clock cycle, which makes the example CPU superscalar. The multiply instructions are completed after 4 clock cycles, which is their latency, when they exit the pipeline. Thus, in the example CPU, 8 multiply instructions are simultaneously executed in each clock cycle, in various stages of the 2 parallel pipelines. Whenever you have independent iterations, e.g. what looks like a "for" loop in the source program, where there are no dependencies between distinct executions of the loop body, the iterations can be executed in 4 different ways, sequentially, interleaved, pipelined or in parallel. The last 3 ways can provide an acceleration in comparison with the sequential execution of the iteration. In the last 2 ways there is simultaneous execution of multiple iterations or multiple parts of an iteration. For parallel execution of the iteration (like in OpenMP "parallel for" or like in NVIDIA CUDA), a thread must be created for each iteration execution and all threads are launched to be executed in parallel by multiple hardware execution units. For pipelined execution of the iteration, the iteration body is partitioned in multiple consecutive blocks that use as input data the output data of the previous block (which may need adding additional storage variables, to separate output from input for each block), then a thread must be created for each such block that implements a part of the iteration, and then all such threads are launched to be executed in parallel by multiple hardware execution units. These 2 ways of organizing simultaneous work, pipelined execution and parallel execution are applicable to any kind of iterative process. Two of the most important such iterative processes are the execution of a stream of instructions and the implementation of an array operation, which performs some operation on all the elements of an array. In both cases one can use a combination of pipelining and parallelism to achieve maximum speed. For these 2 cases, sometimes the terms "instruction-level parallelism and pipelining" and "data-level parallelism and pipelining" are used. The second of these 2 terms is misleading, because not data are executed in parallel or pipelined, but the iterations that process data are executed in parallel or pipelined. For any case where pipelining may be used, it is important to recognize which is the iterative process that can be implemented in this way. For unrelated tasks a.k.a. processes a.k.a. threads, only 3 ways of execution are available: sequential, interleaved and in parallel. The 4th way of execution, pipelined, is available only for iterations, where the difference between iterations and unrelated tasks is that each iteration executes the same program (i.e. the loop body, when the iteration is written with the sequential loop syntax).

adrian_b 2y ago

Nope. 1957 in a transistorized computer is far too late for the origin of pipelining. Pipelining had already been used in computers with vacuum tubes a few years before and it had also been used already a decade earlier in computers with electromechanical relays, i.e. IBM SSEC, which had a 3-stage pipeline for the execution of its instructions (IBM SSEC had a Harvard architecture, with distinct kinds of memories for program and for data). Before 1959, pipelining was named "overlapped execution". The first use of the word "pipeline" was as a metaphor in the description of the IBM Stretch computer, in 1959. The word "pipeline" began to be used as a verb, with forms like "pipelining" and "pipelined" around 1965. The first paper where I have seen such a verbal use was from the US Army. Outside computing, pipelining as a method of accelerating iterative processes had been used for centuries in the progressive assembly lines, e.g. for cars, and before that for ships or engines. Pipelined execution and parallel execution are dual methods for accelerating an iterative process that transforms a stream of data. In the former the process is divided into subprocesses through which the stream of data passes in series, while in the latter the stream of data is divided into substreams that go in parallel through multiple instances of the process.

cogman10 2y ago
The earliest "pipeline" example I can find is the portsmouth block mills [1] implemented by Marc Brunel[2]/Henry Maudslay[3] around 1802 [1] https://en.wikipedia.org/wiki/Portsmouth_Block_Mills https://en.wikipedia.org/wiki/Portsmouth_Block_Mills [2] https://en.wikipedia.org/wiki/Marc_Isambard_Brunel https://en.wikipedia.org/wiki/Marc_Isambard_Brunel [3] https://en.wikipedia.org/wiki/Henry_Maudslay https://en.wikipedia.org/wiki/Henry_Maudslay
- bjourne 2y ago
  Before that you had bucket brigades.
- adrian_b 2y ago
  Wikipedia gives another much more ancient example of a "pipeline", the Venetian Arsenal, which had a progressive assembly line for ships, which had a throughput that could be greater than of one ship per day, and which has been built in the 12th century.
formerly_proven 2y ago
Zuse Z3 had a three stage instruction pipeline.
- adrian_b 2y ago
  If this is true, then it resembles in this feature the IBM SSEC, another electromechanical computer with a three stage instruction pipeline, which however was built only later, after WWII, between 1944 and 1947. The main inspiration for IBM SSEC has been Harvard Mark I, an earlier electromechanical computer built by IBM based on a design done mostly by Howard Aiken, but it would not have been impossible for some information about the Zuse computers to have reached IBM after WWII, contributing to the design of the SSEC.
Voultapher 2y ago
> Pipelined execution and parallel execution are dual methods for accelerating an iterative process that transforms a stream of data. In the former the process is divided into subprocesses through which the stream of data passes in series, while in the latter the stream of data is divided into substreams that go in parallel through multiple instances of the process. With parallel do you mean superscalar execution i.e. having two ALUs or do you mean having multiple cores?
- adrian_b 2y ago
  Parallel execution can exist at many different levels, e.g. at processor level you can have multiple processors executing in parallel some threads. At instruction level, the execution of instructions is an iterative process, so like for any other iterative process parallelism or pipelining or both parallelism and pipelining may be used. Most modern CPUs use both parallelism and pipelining in the execution of instructions. If you have e.g. a stream of multiply instructions, the CPU may have for example 2 multiply pipelines, where each multiply pipeline has 4 stages. The incoming multiply instruction stream is divided into 2 substreams, which are dispatched in parallel to the 2 multiply pipelines, so 2 multiply instructions are initiated in each clock cycle, which makes the example CPU superscalar. The multiply instructions are completed after 4 clock cycles, which is their latency, when they exit the pipeline. Thus, in the example CPU, 8 multiply instructions are simultaneously executed in each clock cycle, in various stages of the 2 parallel pipelines. Whenever you have independent iterations, e.g. what looks like a "for" loop in the source program, where there are no dependencies between distinct executions of the loop body, the iterations can be executed in 4 different ways, sequentially, interleaved, pipelined or in parallel. The last 3 ways can provide an acceleration in comparison with the sequential execution of the iteration. In the last 2 ways there is simultaneous execution of multiple iterations or multiple parts of an iteration. For parallel execution of the iteration (like in OpenMP "parallel for" or like in NVIDIA CUDA), a thread must be created for each iteration execution and all threads are launched to be executed in parallel by multiple hardware execution units. For pipelined execution of the iteration, the iteration body is partitioned in multiple consecutive blocks that use as input data the output data of the previous block (which may need adding additional storage variables, to separate output from input for each block), then a thread must be created for each such block that implements a part of the iteration, and then all such threads are launched to be executed in parallel by multiple hardware execution units. These 2 ways of organizing simultaneous work, pipelined execution and parallel execution are applicable to any kind of iterative process. Two of the most important such iterative processes are the execution of a stream of instructions and the implementation of an array operation, which performs some operation on all the elements of an array. In both cases one can use a combination of pipelining and parallelism to achieve maximum speed. For these 2 cases, sometimes the terms "instruction-level parallelism and pipelining" and "data-level parallelism and pipelining" are used. The second of these 2 terms is misleading, because not data are executed in parallel or pipelined, but the iterations that process data are executed in parallel or pipelined. For any case where pipelining may be used, it is important to recognize which is the iterative process that can be implemented in this way. For unrelated tasks a.k.a. processes a.k.a. threads, only 3 ways of execution are available: sequential, interleaved and in parallel. The 4th way of execution, pipelined, is available only for iterations, where the difference between iterations and unrelated tasks is that each iteration executes the same program (i.e. the loop body, when the iteration is written with the sequential loop syntax).