2
$\begingroup$

Can you pipeline a pure Von Neumann architecture based CPU or do you need seperate data and instruction caches for this? If you include seperate instruction and data caches (then it isn't a von neumann CPU anymore, it's a modified Harvard), how do you unify the data of these caches so that they get stored in a single memory?

$\endgroup$
  • $\begingroup$ If you have separate I and D caches, but they are coherent (writes to the D cache are "seen" by the I cache) then you have a "stored program computer" == "Von Neumann architecture", no? $\endgroup$ – Wandering Logic Mar 5 '15 at 23:34
  • $\begingroup$ @WanderingLogic: no, technically you have a "modified Harvard architecture". $\endgroup$ – Fizz Mar 6 '15 at 1:01
  • $\begingroup$ @WanderingLogic: Since it's a hybrid between the two, you might as well decide to call it "modified von Neumann architecture", but "modified Harvard architecture" is the (much more) established term of art. $\endgroup$ – Fizz Mar 6 '15 at 1:24
  • $\begingroup$ @WanderingLogic: What does that have to do with what I said? Indeed some object to "von Neumann architecture" and call it "Princeton architecture" instead (or nothing at all). But Patterson&Hennessy do mention "Harvard architecture" at least in the more recent versions of their book (albeit in the CD appendinx in the 4th ed.) $\endgroup$ – Fizz Mar 6 '15 at 1:56
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Wandering Logic Mar 6 '15 at 1:56
4
$\begingroup$

A processor that can only support one memory access per cycle can still be pipelined. Such a memory interface would represents a structural hazard for load and store operations. In addition, store operations would introduce the equivalent of a control hazard since they might change instructions that have already been fetched.

The structural hazard can be detected when the instruction is decoded and the pipeline stalled at instruction fetch at the appropriate point. This allows a load or store to execute at the cost of a pipeline bubble. For stores, the processor can speculate that a store does not address memory that holds instructions which will be in the pipeline (or at least that the store not change the semantics of any such instructions). This is comparable to predicting a branch. As branch prediction requires checking the condition and target, store conflict prediction requires a comparison of the store address with the addresses of all instructions that will have been fetched by the time the store data becomes visible to the instruction fetch stage. As a branch misprediction requires flushing the pipeline so would a store conflict misprediction.

If one allows a wider front end and buffering, the impact of the structural hazard can be reduced. Such buffering, even if it is after instruction decode, might be considered a cache.

A processor that breaks some instructions into multiple micro-ops and executes one micro-op per cycle could benefit from such a buffer even if only one instruction is fetched per cycle. Variable length instructions would naturally benefit from a buffer of fetched instructions since a fixed width fetch would often either fetch more than one instruction or fetch only part of an instruction.

If the data access width is greater than the typical instruction length, it also becomes natural to use this greater width for fetching instructions, buffering any excess.

The structural hazard related to loads and stores can avoided by multiporting (or accessing the cache twice within a single cycle) or pseudo-multiporting (banking) the memory. The processor would still have the quasi-control hazard for stores. The main benefits of such an implementation over having separate caches would be somewhat simpler handling of stores and faster operation when running self-modifying code. The processor could still handle the store issue with separate coherent caches, but implementing coherence and handling the delay in realization of stores in the instruction cache would add complexity.

I would argue that a modified Harvard architecture that implements a Von Neumann interface (i.e., is indistinguishable to software except with respect to performance) is Von Neumann. (Recent ISAs generally avoid such guarantees. The benefit of a simpler interface is generally not considered worth the complexity/performance tradeoffs.)

$\endgroup$
  • $\begingroup$ Wouldn't you have to bubble the pipeline on a store because you can either read memory (reading instructions) or storing memory (the store instruction)? $\endgroup$ – gilianzz Mar 5 '15 at 21:04
  • $\begingroup$ @gilianzz Yes. I should have written "allows a load or store to execute". (I made an [obviously incomplete] edit while answering; I had earlier described load and store behaviors entirely separately.) That both have structural hazard issues is stated in the second sentence of the answer. $\endgroup$ – Paul A. Clayton Mar 5 '15 at 21:10
  • $\begingroup$ Could you fix the instruction vs data problem by reading instructions on the clock's rising edge and writing data on the clock's falling edge so no hazards will occur anymore, or will this not work? $\endgroup$ – gilianzz Mar 5 '15 at 21:41
  • $\begingroup$ Re "A processor that can only support one memory access per cycle can be pipelined." What exactly do you mean by this? That it must support at most one, at least one or exactly one access per cycle? And which memory are you talking about in that sentence? The cache(s)? And is that supposed to imply that if this (unclear) requirement is not met, the processor cannot be pipelined? $\endgroup$ – Fizz Mar 5 '15 at 22:05
  • 1
    $\begingroup$ Besides some unclarities like that (I won't go over the rest of them), it seems your answer can summarized as: yes, the [first-level] cache can be unified but there will be more pipeline stalls, so you might want to multi-port it to compensate (at which point you might as well just use separate caches.) $\endgroup$ – Fizz Mar 5 '15 at 22:35
1
$\begingroup$

Apparently the ILLIAC II had a single/unified cache (called a "fast buffer") and a primitive 3-stage pipeline. It looks like pretty much every (pipelined) processor thereafter had split (first level) caches, as long as it had caches. L2, L3+ caches are usually unified though.

There have also been some recent proposals for unified first level cache, e.g. from Intel Spain labs (which I didn't even know existed): "Virtually Split Cache: An Efficient Mechanism to Distribute Instructions and Data" (TACO 2013). The main downside is complexity if you want to preserve good throughput. The reasons for the split L1 cache status quo are explained in the paper as:

While unified approaches usually provide higher hit rates by automatically sharing resources instead of statically partitioning them, split [L1] caches are the preferred configuration, mainly because of the following reasons:

  • Different instructions can access the instruction cache, in the fetch stage of the pipeline, and the data cache, usually in the memory stage, at the same time in pipelined processors. Unified approaches would require several access ports and, thus, more complexity to provide the same advantages.

  • The instruction cache design may be simpler, as it only needs to perform, ideally, read operations.

  • Unified caches of the same aggregated capacity imply higher latencies.

Their "virtually split cache" proposal is somewhere in between as the cache cells are unified but there are two sets of tags and indices and independent ports.

Also note that the dichotomy between Harvard and von Neumann is not that sharp in practice as most general purpose current processors (using a split L1 cache but unified lower levels of memory) are of the so-called "modified Harvard architecture", which is a combination of the best of both worlds. As I said in a comment above, the terminology "modified Harvard architecture" is somewhat arbitrary given that it applies to a hybrid; you might as well decide to call it "modified von Neumann architecture", it's just that the former has been the established term of art. Furthermore, different authors may mean different things by "modified Harvard architecture"; it could mean that the memory is unified and caches are [mostly] transparent so the memory as a whole appears to the programmer as in the von Neumann model, or it could also mean a weaker model in which there are different address spaces for data and programs but there are operations to copy between these; see slide 8 in this presentation, which is one of the comprehensive ones on this topic.

$\endgroup$
  • $\begingroup$ The VSC proposal does not duplicate the tags, instead it dynamically (coarse-grained) allocates a way to either instructions or data. At any given time 1 to 7 ways are allocated to storing instructions and 7 to 1 ways to data. Extra tags (equivalent to tags for two extra ways) are used in one way allocation decision mechanism. $\endgroup$ – Paul A. Clayton Mar 9 '15 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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