# Question
Title: Pros and Cons of Average Memory Access Time When Increasing Cache Block Size
Assuming we have a single-level (L1) cache and main memory, what are some of the advantages and disadvantages of having a larger cache block size (considering average memory access time).

The only ones I can think of are that a larger block size could increase the hit rate when adjacent memory locations are accessed, i.e. good for spatial locality. I can't think of any other advantages; are there?

As for disadvantages, I assume that having a larger block size increases the cache size, thereby increasing cost (since L1 cache is expensive), but I can't see any disadvantages relating to average memory access time. Are there?

# Answer
An increased block size is indeed good for spacial locality.

On the other hand, a large block size increases the possibility of fragmentation and false sharing (in multiprocessor system).

Another way of thinking about this problem is if your cache size is fixed (based on cost, etc.), and you are changing the block size. In this case, as you increase your cache block size, accessing adjacent memory locations will have more hits (spacial locality), but there is a disadvantage considering temporal locality. Consider the extreme case, in which the cache has one block. Of course, this would be good for spacial locality, but it is terrible for a program repeatedly accessing two memory locations that are at least one full block size away from each other. The cache will miss every time.

**EDIT**

Consider this: you have a process with data in consecutive memory locations "A" through "H" of size "1." You have a warm cache of size "4" (ignoring compulsory misses, the misses/repeat below are average case) and an LRU cache replacement policy.

Let the cache block size be 4 (the "largest" block size case).

* For repeated, in-order memory accesses A-H, this cache has 2 misses/repeat.
* For repeated, out-of-order memory accesses A, B, E, F, C, D, G, H, this cache has 4 misses/repeat.
* For repeated, out-of-order memory accesses A, B, E, F, this cache has 2 misses/repeat.
* For repeated, random memory accesses A, E, B, F, this cache has 4 misses/repeat.

Let the cache block size be 1 (the "smallest" block size case).

* For repeated, in-order memory accesses A-H, this cache has 8 misses/repeat.
* For repeated, out-of-order memory accesses A, B, E, F, C, D, G, H, this cache has 8 misses/repeat.
* For repeated, out-of-order memory accesses A, B, E, F, this cache has 0 misses/repeat.
* For repeated, random memory accesses A, E, B, F, this cache has 0 misses/repeat.

Let the cache block size be 2 (the "optimal" block size case).

* For repeated, in-order memory accesses A-H, this cache has 4 misses/repeat.
* For repeated, out-of-order memory accesses A, B, E, F, C, D, G, H, this cache has 4 misses/repeat.
* For repeated, out-of-order memory accesses A, B, E, F, this cache has 0 misses/repeat.
* For repeated, random memory accesses A, E, B, F, this cache has 2 misses/repeat.

The "largest" block size case is best for repeated, in-order memory accesses (best for spacial locality) and worst for repeated, random memory accesses (worst for temporal locality).

The "smallest" block size case is worst for repeated, in-order memory accesses (worst for spacial locality) and best for repeated, random memory accesses (best for temporal locality). It is good for out-of-order memory accesses, depending on the size of the working set.

The "optimal" block size case is good for repeated, in-order memory accesses and good for repeated, random memory accesses, but it is not the "best" for either case.
> 2 votes

# Answer
### Advantages

The advantages of larger block size include: smaller tag storage (or larger cache capacity for a given tag storage budget), greater bandwidth efficiency, memory error correction code efficiency, potentially improved way prediction/memoization, potentially larger access bandwidth, effective prefetching under sufficient spatial locality in the reference stream, and reduced coherence directory overhead (and potentially reduced coherence traffic overhead).

Smaller tags (doubling block size halves the number of tags and removes one bit per tag) can be a significant consideration if tag access latency or storage capacity is a significant concern. In the past (and for huge off-chip caches) greatly reducing the number of tags can make the difference between fitting the tags on chip (with latency and pin-count benefits) and having tags off-chip. Larger cache size (under constrained tag storage) and lower tag access latency have obvious benefits for average memory access time. (Obviously, at extremely small block sizes, the total storage overhead for tags may noticeably impact data capacity.)

(The size of an off-chip cache could also be chosen after processor chip manufacture with little additional hardware cost in the processor chip, previously not uncommon for off-chip L2 caches. Incidentally, doubling block size would also allow doubling the cacheable memory address space with the same tags.)

Greater bandwidth efficiency comes from knowing that a larger chunk of memory will be retrieved. With a given DRAM burst length, the size of an access constraints the width of the interface. (An implementation could always fetch the adjacent cache block of data to gain the advantage for reads at a lower capacity cost, storing such in a small prefetch buffer. Writeback would be more complicated but they are less common and writeback bandwidth constrained workloads would tend to have spatial locality that could be exploited by checking for adjacent blocks.)

ECC encoding is more efficient given a larger block size. While this would not effect the L1 overhead since L1 would handle sub-block writes, the overhead in memory for a given amount of correction would be lower. Fetch size can also impact the practicality of chip-scale redudancy (e.g., IBM's ChipKill). A wider interface can use more DRAM chips with the same commodity bit width and burst length, reducing the overhead to provide a given level of correction even when an entire DRAM chip is unreliable because the fraction of information coming from one chip is less. Memory ECC encoding is typically over chunks smaller than blocks, but extending the encoding beyond fetch units is more complex and adds overhead (in theory, information required for *correction* could be shared over more than one chunk, requiring writebacks to have larger granularity).

A larger block size can also improve way prediction accuracy by reducing choice (all chunks within a cache block that would be separate cache blocks with a smaller block size are in the same way by definition) and exposing greater spatial locality (this improves warm-up and hit rate in some predictors). For partial virtual tag way predictors, larger block sizes increase the number of tag bits available for a given storage budget (which is constrained by latency), increasing accuracy. Way prediction can provide lower access latency. Way memoization for streaming accesses (most instruction cache accesses with modest fetch width and a significant number of data accesses) will be available for more accesses before the way changes.

Larger block size also facilitates higher access bandwidth by facilitating a larger number of banks within the same cache block. By using what is effectively single-cycle tag memoization, any banks within a block can supply data with only a single tag check; a larger block increases the chance that more than one access will be within the block. This does not decrease the latency of an individual access but allows more accesses to be started earlier, reducing the effective average memory access time.

The advantage of effective prefetching under adequate spatial locality of access is the commonly presented advantage. This advantage is reduced given prefetching which can dynamically exploit spatial locality when present without the storage overhead of larger blocks.

The storage overhead for directory-based coherence is also reduced with a larger block size. Full directories store the coherence state for each block, often by tracking it for each memory block, so using a larger block obviously reduces the relative overhead. Similarly, caching directory entries becomes more effective. (Coherence traffic may also be reduced due to spatial locality. As with prefetching, smaller blocks can be used while dynamically choosing larger coherence requests to reduce the number of requests on the network. False sharing increases coherence traffic.)

(Software invalidation of large cacheable regions may also be faster with larger blocks as fewer blocks need to be explicity invalidated.)

### Disadvantages

The disadvantages of larger block size include: wasted bandwidth and storage under lower spatial locality, false sharing issues, high latency if early use is not supported, and higher conflict rate.

Memory bandwidth is wasted when data that is fetched is not used and when data that was not modified is written back to memory (or unnecessarily fetched under read for ownership). With a larger block size, both of these are more likely to occur because spatial locality of accesses is limited. Cache capacity is wasted when data is fetched but not used (for reasonable size blocks, tag storage is much less than data storage, so increased tag overhead with small blocks is generally not significant in terms of total storage capacity).

Under invalidation-based coherence protocols, cache blocks are invalidated when a write is made anywhere with the block by another agent. With larger blocks, more of the block will be invalidated. This false sharing is effectively an expression of limits of spatial locality of writes in a multithread context. This issue can be reduce using sectored cache blocks so that only the sector is invalidated. While traditional sectoring would waste capacity when a significant number of sub-blocks are invalid, larger cache blocks with sectoring may be a good choice. (Sectoring can also facilitate software compatibility when cache block size was exposed.) In theory, instruction and data cache false sharing is also possible, though writes to active code space are discouraged in modern high performance systems.

If the entire cache block must be loaded before any values from it are used, then a larger cache block (with constant bandwidth) will increase miss latency. (In theory, if multiple cache blocks could be fetched from memory in parallel, the fill latency could also impact effective bandwidth if separate buffers were not provided for each potential ongoing fill. Sometimes miss handling might be stalled waiting for a block fill to complete and to free buffer entry; this would be more likely to happen with longer fill latency.)

A larger block size tends to increase the number of conflict misses; with a smaller number of sets, the chance of multiple near-in-time access having the same index is higher. Ironically, spatial locality of access can increase the rate of conflicts under traditional indexing because if one access conflicts, nearby accesses are also likely to conflict. (Skewed associativity could reduce this effect.)

### Overview

With larger caches, the conflict misses from larger blocks are less common because either the number of sets is increased (so the chance of indices matching is lower) or the number of ways is increased (so matching indices are less likely to evict a useful cache block). The larger access latency of larger caches also reduces the latency penalty of higher associativity. In addition, larger caches increase the residency time of a block which tends to increase the spatial locality.

With even the simplest implementation of prefetching (loading all the blocks equivalent to a larger block), the spatial locality based hit rate benefit of larger block sizes effectively disappears while retaining finer-grained replacement choice (and coherence invalidation).

(For L2+ caches, which are not considered in this question, tag storage size can be a significant consideration since such caches are typically accessed with tag-data phasing and farther caches are not probed until a miss is determined. Smaller tag storage then means lower hit latency and lower miss determination latency. In addition, if the tag storage less area-efficient, the cost of tag storage becomes more significant; the SRAM tags with DRAM data storage in some IBM POWER L3 caches is a case where smaller bit count tag storage has a greater benefit.)

64 bytes appears to be a fairly settled block size for "general purpose" L1 caches in part from the commoditization of 64-bit memory interfaces with DRAM burst length of 8 (and software optimizations based on this size) but also matching reasonably well "typical" spatial locality for "typical" capacity L1 caches. Some server-oriented processors use larger blocks in part because larger capacity last-level caches are often helpful (having closer matching of L1 and L2 block sizes can be helpful) and because spatial locality may be more common. Some GPUs use larger L1 cache blocks, presumably to support greater memory bandwidth and access bandwidth with the common case also having considerable spatial locality with weak temporal locality (streaming accesses or nearly so).
> 2 votes

# Answer
Increasing the cache line size while keeping the number of lines constant increases the cache size at massively increased cost. Not something I'd count as disadvantage, you get what you pay for.

I'd assume a fixed cache size, therefore fewer lines. Which is bad if cache lines are only partially used.
> 1 votes

---
Tags: computer-architecture, memory-management, cpu-cache
---


# Question
Title: Can CPU's 'shortcut' adding 0, multiplying by 1, and multiplying by 0?
I am currently writing a program where a lot of adding 0 to numbers and multiplying by 1 and 0 occurs and it got me to wondering if the CPU 'shortcuts' (drops), these operations. I'm a CS student and this hasn't been brought up ever.

Can a CPU do this? What are the trade-offs in designing a CPU that detects +1, \*1 and \*0 and executes them faster?

# Answer
Yes, there are processors which detect some kind of do-nothing operations, handle them specially so that they take less time than what they would take if they were handled naïvely. In some cases, there are even recommended instructions to use for NOP (NOP are sometimes useful to align the code with a memory boundary, having NOP of various lengths available help the relieve the decoding part), the wikipedia page for NOP has a list which gives the normal meaning for some of them.

But

* what you think as a do-nothing operation may not be one if you take into account things like resetting flags or the side effects of memory accesses -- and a processor should behave correctly in such matter;
* I'd not rely on this as an optimization; more as an encoding trick or as a way to reduce the op-code pressure; they are working when the operands are statically known to have no effect and in such cases, the code writer -- human or compiler -- should avoid the operation if possible;
* detecting dynamically that the value has no effect is probably more costly than what would be gained by doing so. That said, some relatively simple processors have operations which take a time which depend on the arguments (for arithmetic operations, don't think I've seen this for something else than integer multiplication and division, or for floating point operations)
> 4 votes

# Answer
Doing this in the processor is less trivial than you think - for example, if you want to handle multiplication by 1 as a special case, you'd want to handle both x * 1 and 1 * x, which means checking two numbers, and then you still have to produce the right result, taking either the first or the second operand. x * 0 is harder; again you have to check two numbers for being zero, plus you need to handle that inf * 0 = NaN and NaN * 0 = NaN, and that a negative number times 0 is -0, not 0. That's an awful lot of checking for a rare case.

There's the problem that it takes time to decide that there's *no* special case. It will take time to stop the processor from proceeding with the multiplication. This may be difficult if a multiplication is designed to take all of the available time.

Now let's say a multiplication takes 3 cycles usually and you could cut it short to 1 cycle. This means you now need the ability that data goes through the processor on two different paths, one single cycle and one three cycle path.

Where it is done is during division, which is usually implemented in a slow and iterative way, for example producing two bits per cycle. Since this is slow and iterative anyway, it is easier to cut the calculation short when the dividend becomes zero, for example dividing 255 / 5 needs only six bits of the result. That can and does lead to a shorter execution time on modern processors.
> 4 votes

# Answer
These optimizations occur in *compilation time* (statically) rather than in *execution time* (dynamically). The code generation part of the compiler will convert addition by the constant 1 to an increment operation, if such an operation is available and faster. Multiplication by 1 will be cut out at an even earlier stage, as is multiplication by 0, which will be replaced by the constant 0, and further optimized. These simplifications are similar to *constant folding*, in which constant arithmetic expressions are evaluated in compile time.

Another question you could ask is whether addition or multiplication of two non-constant numbers is faster if some of the operands are trivial. I doubt that it does for modern CPUs, but in general it could depend on the processor, especially if a certain expensive operation like division is performed sequentially.
> 2 votes

# Answer
*In general*, processors do not detect and special case identity elements (zero addends, zero shifts, one multiplicants, one divisors) or zero multiplicands.

Addition is typically extremely inexpensive; a processor complex enough to handle the identity special case would typically have enough execution width that skipping an occasional addition would not improve performance much. The latency benefit is also low (e.g., zero cycles versus one cycle). The frequency with which such occurs would also be low, so the net benefit would be small at best.

With the noteworthy exception of zeroing idioms, a zero result would be detected near the end of the execution cycle. At that point, the decision to execute the dependent operation has already been made and, in a traditional out-of-order design, the expectation of a result of the dependent operation in one cycle has been used by the scheduler to schedule dependent operations. Dynamically converting the addition to a copy at execution might save a little energy, but detecting the special case of an addition and making the decision for many operations (the common case) would probably use more energy overall.

Zeroing idioms are recognized in decode and handled in register renaming. This removes most of the added cost of zero detection and provides the information early enough that instruction scheduling can be adjusted. As mentioned in this Real World Technologies forum post, Intel does exploit this special case to provide lower latency for some indexed addressing cases where the index has been zeroed using a zeroing idiom.

Because no-page-crossing speculation (and its misprediction recovery mechanism) is broadly useful, adding this special case may have been very inexpensive. Even though such zero-indexed loads would be somewhat rare (e.g., the first load in a loop), the extra cost would be small and load latency is often critical. (While a compiler could convert the first iteration of such loops into direct base + offset addressing, the code bloat effect is obvious and the optimization rather microarchitecture specific. Similarly, function calls with explicit zero operands could be handled specially by the compiler with longer compile times and possible code bloat.)

Special casing addition by an explicitly zeroed operand could be handled in rename, but as noted above the benefit would be modest because additions are cheap in latency and issue width. (Multiplication by an explicitly zeroed operand would be similar, though the benefit would be greater.)

Multiplication is a different; multiplication generally has high enough latency that early output of the result would be easier to implement in terms of scheduling. With a fully pipelined multiplier, throughput would not be improved with early output, but latency would be improved. (In theory, throughput could be improved in a fully pipelined multiplier if two short multiplications were executed in parallel, a kind of dynamic SIMD. Since such would also involve more operands, the extra complexity would not be likely to be justified.)

Motorola's (now Freescale) PowerPC 750 had an unpipelined multiplier and supported early out when a specific operand was small (not just one or zero). This improved both latency and throughput.

While some ISAs have detection of zero results at no additional cost (setting flags on many operations) and this would also make detection of small positivie numbers easy (the most significant bits being zero is part of the specific zero detection), if the potentially special value has a short life (the common case), the opportunity for exploiting such special cases would be small.

If the special value is recognized earlier than other operands are available (or a structural hazard delays start of execution), this extra delay could *in theory* be exploited to strength reduce the operation before it starts execution. When the special value is recognized and the scheduler has decided not to execute the operation (data or structural hazard preventing execution or even energy management throttling execution), the operation could be strength reduced before the next scheduling opportunity. This does not seem likely to be low hanging (nor high value) fruit.

Other tricks might be used to hide the scheduling loop latency to facilitate such dynamic strength reductions, but professional hardware designers have not yet chosen to perform such strength reductions so the cost and benefit tradeoffs are presumably not favorable (under expected conditions).
> 1 votes

---
Tags: arithmetic, cpu
---


# Question
Title: Assumption of a generation of the dataset by a probability distribution
Consider the following paragraph from the deeplearningbook

> **The training and test data are generated by a probability distribution over datasets called the data-generating process.** We typically make a set of assumptions known collectively as the i.i.d. assumptions. These assumptions are that the examples in each dataset are independent from each other, and that the **training set and test set are identically distributed, drawn from the same probability distribution as each other. This assumption enables us to describe the data-generating process with a probability distribution over a single example. The same distribution is then used to generate every train example and every test example. We call that shared underlying distribution the data-generating distribution, denoted $p\_{data}$**. This probabilistic framework and the i.i.d. assumptions enables us to mathematically study the relationship between training error and test error.

Bolded area is difficult for me to comprehend. Here I have the following issues in interpreting.

1) How probability distribution is generating a dataset?

2) Are the **generation process** and **probability distribution** the same?

3) What is the **sample space** and **random experiment** for the underlying probability distribution?

# Answer
The main takeaway from this paragraph is that the authors assume that the training data and test data are sampled i.i.d. from the same distribution, because then if we are able to estimate some statistic of the distribution we sample the training data from, we will be able to do the same on the test data.

As for your specific points:

> 1) How probability distribution is generating a dataset?

We sample from a large set according to some distribution. The precise method depends on the problem.

> 2) Are the generation process and probability distribution the same?

No, the generation process provides a sample from a distribution. A probability distribution is an abstract mathematical object, while a generation process is a specific algorithm that provides a dataset. In a way, the distribution provides a probabilistic description of what the generation process should return.

> 3) What is the sample space and random experiment for the underlying probability distribution?

The sample space depends on the problem in question. I'm not sure what you mean by 'random experiment', but the definition of the random distribution is problem-specific.
> 1 votes

---
Tags: probability-theory, statistics
---


title: Doubt on Graph on DFS

text:
# Question
Title: Doubt on Graph on DFS
The maximum number of edges possible in an undirected graph with 5 nodes, when DFS call made on any random node in the graph result stack size 5 i.e. 5 function call present in stack simultaneously are \____________________

---

How graph edges can be converted to a function call ? Is that mean here we have to do a recursive call. I am not getting clear, what is function call here. Plz help

# Answer
> 2 votes
Graph edges are not "converted to function calls". DFS is a recursive function. When you call DFS on some start node, it looks at the adjacent vertices (vertices which are connected to this node via an edge) and recursively calls itself on one of them.
But since each node is only visited once in a DFS, the maximum stack size cannot be greater than the number of nodes.

---
Tags: algorithms
---


# Question
Title: What are the disadvantages of having many registers?
IA-64 is an architecture that has 128 general purpose registers, are there any disadvantages (beside being more expensive and larger instruction size) to having many registers?

# Answer
> 4 votes
The disadvantage is higher latency per instruction. Either you need to run the processor clock slower or you need to pipeline the register file, so each instruction will take more cycles. (Pipelining the register file is difficult, and rarely done.) A register file is a physical thing, thus must obey the laws of physics. (In particular, that our universe has only three spatial dimensions, and that the speed of light is a constant.) Suppose your register file is 2 dimensional (as all are today). Then the register bits are typically arranged in a rectangle with width $b$ (where $b$ is the number of bits stored in each register) and height $N$ (where $N$ is the number of registers.) (This assumes that the circuit to implement the bit is approximately square.)

Here's a picture of a 3-ported 4x4 register file that I found at http://gyan.fragnel.edu.in/~surve/COA/ISA/Images/Figure4.37.jpg:

Each time you read a register you need to propagate a read-enable signal to each bit of that register across the width of the array. If the read-enable wires are buffered then the delay to propagate a signal down the wire is proportional to the length of the wire. (Neither the horizontal nor vertical wires in this diagram are buffered. Buffering the vertical wires is actually hard, because that's a many-to-1 bus, not a 1-to-many point-to-point signal, so you may not be able to do that at all. In the case that you can't buffer a wire, the wire will have a delay proportional to something like the square of the length of the wire.)

So *at best* a register file access is going to take time proportional to $O(b+N)$. (That doesn't count the time for the decoder, and assumes that you somehow figure out how to buffer all the wires.)

To sum up: the more bits you are storing, the slower the storage.

# Answer
> 3 votes
As noted in the question, increasing the number of registers *tends* to increase instruction size (clustering, functional specialization, windowing, and other features can reduce the encoding overhead of a larger number of registers) and the area used by the core.

As Wandering Logic's answer notes, a larger register file will have higher access latency. Increasing cycle time to avoid pipelining register file access has obvious performance implications. Pipelining register file access complicates the design of the register file and the forwarding network (results from more cycles will be sourced from the forwarding network rather than the register file). (The Alpha 21464 was designed with three cycle register file access latency and register caching to simplify forwarding. "Design of an 8-wide Superscalar RISC Microprocessor with Simultaneous Multithreading", Ronald P. Preston et al.: IEEE reference.) Pipelining introduces inefficiencies as well with latch overhead, clock skew, stage imbalance, etc. Process variation may also discourage longer pipelines because the timing for a given core is constrained by the pipeline stage with the longest delay.

(Width pipelining, where part of a value is available earlier, can also reduce the latency for some uses that do not require the full value at the start of execution. A width-pipelined (a.k.a. staggered) ALU (which can provide bitwise logical operations, addition/subtraction, and left shift) could tolerate extra latency for the more significant bits of a value. Similarly, address generation for a load could provide cache index and enough virtual address tag bits for a decent way prediction with only 24 bits available initially. Obviously this technique could be applied to a smaller register file, but the benefit of a faster clock has diminishing returns.)

Access energy is also increased. Power delivery and thermal dissipation are significant design issues in modern high performance processors.

If a register alias table is used to support register renaming under out-of-order execution, the access cost of such is also increased like the register file and the size of each entry will be larger because renaming increases the number of registers.

For in-order execution the cost of determining result availability and selecting a result is also increased because the number of bits in a name is increased. (This effect is present for out-of-order execution as well. With only 32 architected registers, supporting 32 uncommitted results only requires 64 names, so source readiness only involves 6-bit compares; with 128 architected registers, more than 7 bits would be needed to name a register. This can be avoided by only checking for pending result names, but such introduces some complexity.)

Checkpointing register state for speculation recovery also becomes more expensive. Checkpointing would apply to some (not yet implemented) out-of-order execution designs and some forms of supporting transactional memory.

If each context is required to be full-sized, a larger register set makes multithreading more expensive. (For highly ported register files, additional register sets can be provided at lower cost under the restriction that different sets cannot be accessed at the same time. This three dimensional register file technique was developed for SPARC's register windows and used for Itanium's switch-on-event multithreading.)

As robot\_s's answer notes, the cost of context switches increases. The cost of function call save/restore depends on the call interface. Itanium provided stacked integer registers rather than a generic function call interface, so there were not fixed registers to be saved and, in theory, save and restore could be handled asynchronously and involve a separate storage area (avoiding data cache thrashing). Whole-program optimization could also avoid some register save and restore that would be required from a static function interface.

Multicycle register file access also increases the number of cycles between when a fetch address is used (speculatively) and when it is confirmed or corrected (i.e., the branch misprediction penalty increases).

With a "flat" register set, software would tend to assume all registers have equal access cost and are fully paid-for (i.e., "free"). This makes some hardware optimizations more difficult;. Clustering, windowing, hierarchical capacity, exposed banking and other *architectural* features can reduce the impact of larger context storage (but make software optimization more complex and constrain hardware implementations).

The benefit of having a large number of registers depends on the workload and the latency and parallelism of the hardware. Fujitsu's SPARC64 VIIIfx provided more registers than Itanium, but specifically targeted high performance computing.

Itanium was designed under the assumption of static scheduling and high instruction level parallelism with support for single-stepping (so a register name cannot be used under the shadow of execution latency). High ILP means many results per cycle, and results would "occupy" the register for the entire execution latency in addition to any use lifetime. Static scheduling (especially with predication to increase the size of extended basic blocks) tends to increase the number of architectural registers used in order to cover latency and provide parallelism. Itanium also supported "prefetch" of values into registers, where the value would be reloaded if there was a store to the address of the load before the value is used; this would naturally increase register pressure (the register name is taken from the moment the load instruction issues just as with other instructions, so a load advanced ten cycles before use effectively wastes that register name for ten cycles).

# Answer
> 2 votes
Expensive context switch, save and restore all these registers. Some works (more info on William Stallings book) points that with compiler optimization theres almost no improvement when processor has more than 64 registers.

---
Tags: computer-architecture
---


title: Kth smallest element in an arra

text:
# Question
Title: Kth smallest element in an arra
What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?

# Answer
> 1 votes
You can use quickselect with median of medians to find a good pivot so that the total running time is linear in the worst case.

---
Tags: sorting, arrays, search
---


# Question
Title: Why we need to read memory on a write-miss?
I noticed that in write-back caches, when the cpu wants to write to a block, it fetches the block from memory and then updates it. If the block is going to be overwritten and changed by processor, why does the cpu need to read that block from memory?

# Answer
Because write-miss happens only with just a word missing in a block. So all of the block which contains that word must be fetched and then that special word must be updated.
> 3 votes

# Answer
While it would be possible to construct a 128-bit wide memory bus with a separate write-enable control for each octet (sixteen in all), doing so would generally be more expensive than designing the bus to require that any operation which writes to any byte in a 128-bit cache line must supply data for all sixteen. Although there are times when being able to update some bytes in a line without having to read the others would yield a performance advantage, in many cases the penalty of having to fill a cache line from memory *sometime* between when the fist write gets posted and when the line gets flushed will be minimal, and the benefits of eliminating that penalty may be insufficient to justify the cost of the extra write-control logic.
> 3 votes

# Answer
There are several issues involved in this design decision. Since conventional DRAM does not support finer-grained write enable (graphics memories often do), when the data was eventually written back if an entire memory access chunk (often cache block sized) was not written then a read would be necessary. Since conventional DRAM interfaces have significant read-write turnaround latency (and the DRAM row is kept open), performing a read-merge-write at cache block writeback can reduce memory throughput.

Even with finer-grained write enable, cache blocks would have to track validity at the granularity of writes (assuming write allocate). This would add some overhead in cache metadata (e.g., 64-bits for a straightforward byte granular validity tracking of a 64-byte cache block, potentially nearly tripling last level cache metadata — a 4 MiB 16-way cache for a 40-bit address space would have 22 tag bits per block and a few bits for coherence).

The common case is assumed to be the presence of spatial locality and non-complete overwriting. I.e., other data in the written-to cache block will be read before it is written back. Streamed writes are a somewhat frequently occuring case where complete cache blocks are overwritten, but such are also often non-temporal writes that one would prefer not be allocated to the cache. While determination of non-temporal write streams is usually pushed to software, because of the temporal proximity of such writes it would not be extremely difficult for hardware to manage them. (Some x86 string operation implementations do exploit complete overwriting of cache blocks.)

Some instruction sets provide cache block zeroing and/or cache block allocating instructions which allow software to avoid reading memory when entire cache blocks are overwritten (or will have "don't care" data values). Such could be useful for smaller streaming writes (where the buffering benefit from cache allocation is greater than the cache pollution penalty or where reuse while in cache is more likely) and memory allocation (where hardware zero initialization would be a benefit beyond the avoidance of read for ownership).

Having per-byte validity for cache block contents would also complicate cache coherence and consistency. With block-granular data presence, a read coherence request need only specify the cache block. Even if only a single caching agent can hold a partially dirty block (similar to the single owner model for cache coherence), multiple caches might need to provide the data for a request as clean bytes might be resident in another cache with the dirty bytes invalidated.

(Finer-grained validity tracking can have an additional benefit in reducing false sharing.)

Another waste of bandwidth in typical caches is the writeback of modified memory with dead values. For example, when a stack frame is freed, the values are dead but hardware does not know that the modified cache blocks have no modified live values and so it must writeback such blocks (writebacks to memory would only happen if the extent of the stack was smaller for a long enough period). Similarly, when a program ends it will typically leave a lot of modified dead values in cache. Such are not common occurances, but they demonstrate that there is potential for improvement.
> 1 votes

---
Tags: cpu-cache
---


# Question
Title: How can a CPU access more memory locations than 2^wordsize?
I noticed that CPU's like the 8086 and especially the 8080 have the ability to access more memory than what one would normally assume. The 8080, for example, has an 8-bit word size but can use a 16-bit memory address. From what I understand, a standard instruction has the opcode in the beginning and then the address on which it will work. How then, could a 8-bit processor be able to fit an opcode and 16-bit address in 8-bits?

# Answer
The 8080, as @TEMLIB pointed out, had 16 bit registers (the program counter, the stack pointer and BC, DE, and HL), and could access 216 bytes of memory. The 8080 had an 8-bit bus, and for instructions that required 2 bytes of data or address the bus would be used for 2 cycles.

The 8086 is more interesting. The 8086 had 16 bit registers, but could access 220 bytes of memory. It did this by using segment registers. There were four special 16-bit registers, `CS`, `DS`, `ES` and `SS` and every address was calculated by taking 16 times the appropriate segment register plus the 16-bit *offset* coming from a "normal" register. So for example, instruction addresses were all calculated as an offset from `CS * 16`, and stack references were all calculated as an offset from `SS * 16`.

Modern 32-bit processors can also sometimes access more than 232 bytes of DRAM through the virtual memory system. Each running program can access only 232 bytes of virtual memory but the page table entries map to (for example) 36 bit physical addresses, allowing the operating system to run multiple programs simultaneously that collectively can access up to 236 bytes of physical DRAM.
> 8 votes

# Answer
In a 8 bits CPU, all registers do not need to be 8bits wide. The program counter, or index registers, or register pairs, can be used as 16bits registers.

You should look at the 8080 instruction set, or another 8bits CPU, and get the difference between "inherent", "implicit", "indexed", "immediate" types of instructions.
> 2 votes

# Answer
Most CPU architectures use instructions of varying length. Even so-called RISC architectures with "fixed" instruction sizes support additional instruction operand words after the opcode word that determines the basic format of the instruction.

The x86 instruction set, famously, has instructions that vary wildly from 1 byte (8 bits) to as many as 15 bytes.

So, in the old 16-bit real mode x86 CPUs, an instruction to load from a fixed address in memory would normally be encoded in 3 bytes: one *opcode* byte to specify the instruction and the destination register and two additional *operand* bytes to specify the source memory address.
> 2 votes

# Answer
The size of addressable memory is not limited by the size of the memory data bus, the size of instructions, the size of arithmetic operands (e.g., register size), or even the size of addresses used by applications.

A processor can provide instructions larger than the data bus, allowing direct (absolute) addressing of a larger memory. For the 8080, immediate data was generally provided after the byte containing the opcode and not constrained to less than one byte (to allow space for the opcode) or even to one byte. This means that an instruction will take more than one memory cycle to fetch, but this can be an acceptable choice when memory is fast relative to processing and cost is a primary constraint. (This was more a historical consideration.)

(It is also possible to shift instruction constants to provide access to a greater range of aligned addresses.)

A processor can also choose not to provide direct addressing of the entire address space from instructions, allowing the largest instruction to be smaller than the size of addressable memory. Base plus offset addressing can provide access to an address space whose size is based on the size of the base address. The base address can be loaded from memory or using multiple instructions.

The size of the memory data bus also does not limit the size of base addresses (e.g., registers). The 8080 had a 16-bit Program Counter and a 16-bit Stack Pointer. The 8080 also allowed a register pair to be used to address memory. (Using register pairs for memory addressing is not uncommon for 8-bit processors.)

Providing larger special address registers is a somewhat common method to extend addressability. When these address registers do not have to be commonly saved and restored, their size can mostly be hidden from application software. The distinction between specialized segment registers and extended special address registers can be somewhat fuzzy.

Using segments is similar to using register pairs. Intel's 8086, HP's PA-RISC, and AIM's (Apple, IBM, Motorola) PowerPC provided segment registers that extended the addressability provided by registers. The 8086 implied the segment register by the base address register used with the offset in the segment register shifted by four and added to the base address. 32-bit PA-RISC could specify the segment in the instruction or by the two most significant bits in the address with the segment value being inserted as the most significant 32-bits (ORed in for the 64-bit ISA). 32-bit PowerPC used the most significant four bits of an effective address to specify a segment which was appended to the 28 bit inset.

(Bank switching is effectively a form of segmentation where the segment translation applies to all accesses, similar to PowerPC segments, but with typically very limited extension of addressability.)

Base registers (used to provide some degree of virtual addressing to allow multiple programs to see a full-sized address space) are a limited form of segment registers, whether applied to code only, code and data separately, or code and data with a common base offset.

A somewhat common ISA feature of indexed addressing also provides a mechanism to modestly extend addressability when the index is shifted by the size of the operand. This is more of a theoretical possibility.

Page-based address translation provides yet another method of allowing access to a larger physical address space. In page-based address translation, a virtual address is composed on a page number (potentially extend with an address space ID) and a page offset. For every valid page number, a base address (page frame number) is provided to which the page offset is added/inset. The size of this base address is independent of the size of registers. This is similar to PowerPC's use of segmentation to extend the effective address but using, e.g. in a 32-bit address with 4KiB pages, 20 bits of the effective address to specify the segment.
> 1 votes

# Answer
We should distinguish between what are termed the logical address and the physical address. The logical address is the address which an individual program uses. This depends on the instruction set, and is usually limited by such things as how big the address fields are in instructions and how many bits are in an index register. For example, all registers in a PDP-11 were 16 bits, and the biggest address field in an instruction was 16 bits, so any one program could ordinarily address up to 2^16 = 65536 = 64K bytes of memory.

Very quickly after the PDP-11 was introduced, it became apparent that users needed more physical memory. So memory-mapping hardware was designed. Under control of the operating system, the memory map would convert a 16-bit logical address into an 18-bit physical address (this was later expanded to 22 bits). So there could be many programs in memory at the same time, but each one could only address 64K. Part of the OS's job was keeping track of which blocks of physical memory were assigned to which blocks of logical memory for each program. Every time there was a process switch (i.e., when one program paused so another could run), the OS had to update the memory map.

Modern machines use virtual memory, but the memory mapping works essentially the same way.

Some 32-bit x86 processors use PAE (Physical Address Extension), which lets them address up to 2^36 bytes of physical memory, although each program is still limited to 2"32.

One of the designers of the PDP-11, Gordon Bell, devised Bell's Law, which basically says that you need an extra address bit every two years. That is, memory size doubles every two years. If you plot the maximum size and the average size of memory delivered in a PC, this has roughly held true for the past 40 years.
> 0 votes

# Answer
Just because a processor is "8-bit" doesn't mean all of its types and registers are 8-bit.

Case in point: the MOS 6502 processor. It has an 8-bit accumulator A, 8-bit index registers X, Y, and S, a 6-bit flags register P, a 16-bit program counter, and a 16-bit internal register to hold the operand address. Various addressing modes act on this operand address register.

* **Absolute:** `LDA $2002` loads 0x2002 into the operand address register, reads a byte from that address, and writes the value to register A.
* **Indexed:** `STA $3FF0,X` loads 0x3FF0 into the operand address register, adds register X to that value (which may produce a carry), and writes the value in register A to that address.
* **Indirect indexed:** `LDA ($02),Y` reads memory addresses 0x0002 and 0x0003 into the operand address register, adds register Y to that value (which may produce a carry), reads a byte from that address, and writes the value to register A. This is used for large arrays, as the program can add 1 to Y after reading each byte and then add 1 to the value at 0x0003 when Y wraps around to 0.

Because the 6502's ALU is still 8-bit, the CPU adds the least significant byte first and takes an extra cycle to perform a second 8-bit addition if there is a carry.

The CPU uses 16-bit addresses, which means it can see 216 = 65536 bytes (64 KiB) of memory at once. To go beyond this, several computers that use a 6502 processor implement bank switching, a memory controller feature that controls which parts of physical memory are visible to the CPU by changing values on the memory's upper address lines.

* The Apple IIe can switch a 12 KiB "language card" window (addresses 0xD000-0xFFFF) between ROM and RAM, and it can switch the 4 KiB subwindow (0xD000-0xDFFF) between two 4 KiB banks.
* The Family Computer (called Nintendo Entertainment System outside Japan) has bank switching circuits on the Game Pak's circuit board. These circuits, called "mappers", switch banks of ROM or RAM on the cartridge into windows 8 KiB to 32 KiB in size. There are well over a hundred different variants on NES mappers.
* The PC Engine (called TurboGrafx-16 outside Japan) has a HuC6280, a customized version of Rockwell's 65C02 with an integrated MMU that controls eight 8 KiB windows.
> 0 votes

---
Tags: computer-architecture, operating-systems, memory-management, memory-hardware
---


title: Find the flaw in the P != NP proof

text:
# Question
Title: Find the flaw in the P != NP proof
Find the flaw in the following proof that P != NP:

"We are going to show that P != NP using the following steps:

---

1. Describe a problem.
2. Show that said problem is a NP problem.
3. Prove that the lower bound for any algorithm that solves the problem is exponential using an adversarial argument (similarly to showing lower bound on comparison based sorting).
4. Conclude that since the problem is in NP but cannot be solved in polynomial time it is not in P. Thus, P != NP.

---

1. Consider decision problem of determining whether there exists a combination of chemicals (a subset) that mix into the philosopher stone from a set of chemicals S\[1...n\]. We can determine whether a given set of chemicals combines into the philosopher stone using a checking function IsPhilosopherStone(C\[1...m\]) and this function is the only way to determine whether said chemicals produce the philosopher stone. IsPhilosopherStone(C\[1...m\]) takes constant amount of time $\theta(1)$ for all inputs.
2. We can show the problem is NP by designing a verifier verifyPhilosopherStoneCombination(S\[1...n\], w) where w is the witness; the subset of chemicals which produce the philosopher stone as such:

verifyPhilosopherStoneCombination(S\[1...n\], w):

if w $\not\subseteq$ S\[1...n\] say "no"

if IsPhilosopherStone(w) != "yes" say "no"

say "yes"

Checking whether w $\not\subseteq$ S\[1...n\] takes $\theta(n^2)$ in worst case using a naive approach and using IsPhilosopherStone(w) takes $\theta(1)$, so our verifier correctly verifies a given witness in polynomial time so the problem must be in NP.

3. We know we can also solve the problem deterministically in $2^n - 1$ steps by generating the powerset of S\[1...n\] which has length $|P(S)| = 2^n$ and running the verifyPhilosopherStoneCombination() on each set in the powerset (except the empty set, hence $2^n - 1$ steps).

Now consider an alternative algorithm $A$ which would solve the problem in $2^n - 2$ steps or better in the worst case. Since there are $2^n - 1$ non-empty sets in the power set $P(S)$ and using verifyPhilosopherStoneCombination() to check whether a set combines into the philosopher stone takes 1 step we know there must be at least 1 non-empty set that wasn't checked by $A$. Make that set the set that combines into the philosopher stone. $A$ yields an incorrect answer. This means the lower bound for any algorithm that solves the problem is $\Omega(2^n)$.

4. We have shown a problem that is in NP but no in P. Thus P != NP."

# Answer
> 1 votes
I can see some flaws in your argument:

1. first of all (correct me if I am wrong but this is what I understand from your text), your problem can be solved in linear time because it's just a search trough a set of values.
2. Second but more important, your problem is not a decision problem: ***P*** and ***NP*** are complexity classes defined on decision problems.
3. > We have shown a problem that is in NP but no in P. Thus P != NP.

This is were things get confused... your algorithm ***A*** is in NP so i dont get how comparing it with the original algorithm (also in NP) prove that ***P!=NP***

---
Tags: complexity-theory
---


# Question
Title: Is there a path of length $k$ between given vertex to a subset of vertices in a connected directed graph
I am trying to find an efficient algorithm that on input $ (G,s,A,k) $ returns true iff $G$ is a connected directed graph, $s$ is a vertex in $G$, $A$ is a set of vertices in $G$ and there is a path of length $k$ from $s$ to a vertex in $A$

What is the best run time we can get here?

I am currently stuck with this slow algorithm (there might be some minor problems but the concept is of the importance) $T$ that on input $(G,s,A,k)$:

for all vertices $t$ in $A$:

if $k=1$ and $t$ is a neighbor of $s$ return TRUE

if $k=0$ and $s=t$ return TRUE

for all neighbors $r$ of $s$ return $T(G,r,\\{t \\},k-1)$

this algorithm is rather slow because it exhausts all possibilities.

\*cycles of any size (1 or more) are allowed in the graph and in the paths

# Answer
From the algorithm you describe and the comment you made on your question I understand that you are interested in walks and not in simple paths and that the graph is unweighted.

The algorithm you describe has at least exponential complexity since you examine each possible subset of $A$ (it has $2^{|A|} = O(2^N)$ subsets). We can use a much faster polynomial time algorithm.

One such algorithm has $O(k(N + M))$ computational complexity. You will need $k + 1$ boolean matrices, $B\_0, B\_1, \dots, B\_k$, of size $N$. $B\_0$ will be initialized to false, excluding its $s$-th position which will be initiallized to true. That is:

$B\_0\[u\] = 1$, **iff** $u = s$

You will execute $k$ steps. In the $i$-th step you will calculate $B\_i$ using the following formula:

$B\_i\[u\] = 1$, **iff** $\exists v: (v, u) \in E \wedge B\_{i - 1}\[v\] = 1$

This way $B\_i\[u\]$ will be true iff there is a walk of length $i$ from $s$ to $u$. When you have calculated $B\_k$ you can find the answer by checking $B\_k$'s positions that match to $A$'s nodes' ids. Iff at least one of these array positions make $B\_k$ true, then the answer is positive. The computational complexity of this algorithm is $O(k(N + M))$ and its space complexity is $O(kN)$. You can drop the space complexity to $O(N + M)$ if you observe that only the previous and the current boolean matrix $B\_{i - 1}, B\_i, \forall i \in \\{1, 2, \dots, k\\}$ are needed during each step. Bellow you can see a C++ implementation of this algorithm.

```
#include <iostream>
#include <vector>
using namespace std;

#define MAXN 100005  // Equal to maximum possible N + 5

vector<int> E[MAXN];  // Adjacency lists
vector<int> A;  // Nodes that belong in set A

bool PB[MAXN];  // boolean array of the previous step
bool B[MAXN];  // current boolean array

int main()
{
    int N, M, S_A, s, k;
    // N: number of nodes
    // M: number of directed edges
    // S_A: size of set A
    // s: starting node
    // k: length of walk to be done
    cin >> N >> M >> S_A >> s >> k;
    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);  // there is an edge from u to v
    }
    for (int i = 0; i < S_A; i++)
    {
        int a;
        cin >> a;
        A.push_back(a);  // a belongs to A
    }

    // Create B_0
    for (int i = 0; i < N; i++) B[i] = false;
    B[s] = true;

    // Perform the k repetitions
    for (int i = 1; i <= k; i++)
    {
        // Copy B (B_i) to PB (B_{i-1}) and initialize B
        for (int j = 0; j < N; j++)
        {
            PB[j] = B[j];
            B[j] = false;
        }
        for (int j = 0; j < N; j++) if (PB[j])
        {
            // There is a walk from s to j of length i-1...
            for (int l = 0; l < E[j].size(); l++)
            {
                // ...and an edge from j to E[j][l]...
                B[E[j][l]] = true;
                // ...so there is a walk of length i from s to E[j][l]
            }
        }
    }
    // Now B = B_k

    for (int i = 0; i < S_A; i++)
    {
        int a = A[i];
        if (B[a])
        {
            // There is a walk of length k from s to a
            cout << "YES\n";
            return(0);
        }
    }
    // There is no walk of length k from k to any node of A
    cout << "NO\n";
    return(0);
}

```

This algorithm is fast if $k$ is small but when $k$ becomes larger its computational complexity increases significantly. We will now describe an algorithm which is faster for large values of $k$.

You can use the fact that the $(i, j)$ cell of $Adj^p$ (where $Adj$ is the adjacency matrix of the graph) is equal to the number of walks from $i$ to $j$ in the graph with length equal to $p$ (easy to prove using mathematical induction). In your case you are interested in walks of length equal to $k$ so you have to calculate $Adj^k$. You can efficiently calculate $Adj^k$ in $\lceil log\_2k \rceil$ steps using exponentiation by squaring. Each step of the above calculation requires squaring an $N \times N$ matrix. This can be done in $O(N^3)$ using the naive algorithm or in $O(N^{2.373})$ using the fastest known algorithm. The fact that you want to know if a path between two nodes exists and not the number of different paths allows you to avoid large numbers by making the integer matrix boolean after each multiplication. When you have $Adj^k$ (in boolean format) you can check if there is a path of length $k$ from $s$ to a vertex in $A$ by checking the $s$-th row of $Adj^k$ and specifically the columns regarding nodes of $A$. Formally the result is positive iff $$\exists u \in A: Adj^k(s, u) = 1$$ The algorithm is the following:

1. Read input and calculate adjacency matrix of the graph: $O(N^2)$
2. Calculate $Adj^k$ using exponentiation by squaring, fast matrix multiplication and making matrix boolean after each multiplication: $O(N^{2.373}logk)$
3. Check if there exists a cell $Adj^k(s, u) = 1$ where $u \in A$: $O(N)$
4. Output the reslt: $O(1)$

The total computational complexity of this algorithm is $O(N^{2.373}logk)$ and it is better than the first algorithm for large values of $k$. Both of them also include possibility of self edges as you mention in your comment on your question.

You are able to combine the two algorithms and run the fastest one based on the values of the parameters and achive $O(\min \\{k(N + M), N^{2.373}logk\\})$ computational complexity.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Which is faster operations on register operands or immediate operands?
I am reading the book Computer Organization and Design. It compares instructions on memory and instructions on registers but doesn't say anything about the speed of instructions when the source operand(s) is/are constants. In that case which will be faster register operands or immediate(constant) operands ?

# Answer
> 2 votes
# It depends.

Like AProgrammer said, it depends on the processor.

We are in an age where there are many limiting factors based on physics in CPU construction. This means that distance traveled for an instruction and heat generated by a gate cause latency. In theory, this means that for a pipeline where the bottleneck is the decoding stage, this matters. With immediate operands, you would not need to travel to the register to grab the values, which is additional clock cycles and distance traveled. This would decrease latency, and thus increase speed.

However, in real world applications, this is very likely NOT the bottleneck, and so there will be little to no increase (if mandatory register access stages exist) in speed.

# Answer
> 1 votes
The relative performance of instructions using different operand types is somewhat dependent on the instruction set, the processor design, the code being executed, and even the execution environment.

With fixed length instructions (and constant operands that fit within the instruction format), there is no code size penalty for immediate operands and likely no decoding penalty, so even when the pipeline does not provide an advantage to using immediates the avoidance of using a temporary register and an extra load could give the use of immediate operands a performance advantage. (Even in this case, it is conceivable that instructions might be cached in a decoded format that causes code with many or larger immediates to be larger in the decoded cache than functionally identical code that did not "overuse" immediate data.)

The use of a temporary register (which could be avoided with load-and-operate instructions) increases register pressure, reducing the compiler's ability to retain values in registers. In a simple microarchitecture, such might also increase the register port pressure (a modestly more complex design would get the value by forwarding from the load operation and not from the register file) which might delay execution of other operations.

With out-of-order execution, an immediate operand is guaranteed to be available while a register operand would typically have to have its availability determined dynamically. This can be used to simplify the scheduling of operations. (A processor could predict that one operand will be the last available and so only have to check that operand's availability to speculatively decide the operation is ready for execution, later confirming availability of other operands and recovering from any wrong speculation.)

Immediate operands have the advantage of being implicitly prefetched via the instruction stream from reading cache block sized chunks from memory (i.e., immediates exploit spatial locality in the instruction stream). (In addition, accurate prefetching of the instruction stream is much easier than general data prefetching.)

The spatial packing of opcode and data can also be exploited by hardware; it is easier to read one 64-bit chunk than two independent 32-bit chunks.

In some cases the early availability of immediate operands in the pipeline can be exploited to improve performance. The most common example of such an optimization is the calculation of PC-relative addresses, which can be done before register read in the pipeline. A much less common example would be optimizing constant shift amounts; being able to "warm up" the shifter with the shift amount can reduce latency.

Immediate values also facilitate some predecode and trace cache optimizations. This is similar to how a compiler can perform some optimizations from knowing that a value is constant or within a certain range. The processor can use dynamic information unavailable to the compiler and estimate that fix-up costs would be less than the benefit from the operation. (Placing small values in the Register Alias Table is more convenient with immediates; the value will be known to be small and known when the RAT entry is normally written.)

Since a register operand is generally required anyway and some operations do not use immediates, pipelines are typically designed with limited exploitation of early immediate availability.

Aside from the obvious disadvantage of immediates being expensive to modify in most modern processors, immediates can also increase code size. The performance impact of greater code size is highly variable.

It is also worth noting that in some cases memory operands can be as fast or faster than register operands. This can be a consequence of port count constraints (where the cache ports provide extra means of sourcing operands) or specialized cache optimizations such as signature cache, stack cache, knapsack cache, etc.

---
Tags: computer-architecture
---


title: MAXSAT approximation

text:
# Question
Title: MAXSAT approximation
We have been studying a 1/2-approximation for MAXSAT which runs in expected polynomial time, by randomly assigning True/False to each variable and repeating until we reach an assignment with at least half of clauses satisfied.

I don't understand why the algorithm needs to be so complicated. Why does the following not give a 1/2-approximation for MAXSAT in guaranteed linear time?

* Let $m$ be the number of clauses in the formula.
* Set all variables to true. Count the number of satisfied clauses. If it's at least $m/2$ then return this assignment.
* Set all variables to false. Return this assignment.

Every clause contains at least one literal which will be satisfied either by setting a variable to true or a variable to false. Thus the two assignments satisfy a total of at least $m$ clauses so at least one of them satisfies $\ge m/2$ clauses.

# Answer
I won't speculate about your teacher's reasons for including the random assignment algorithm over yours. However, one advantage of random assignment is that, if every clause has at least $k$ literals, it's actually a $(1-2^{-k})$-approximation (Wikipedia cites this to Vazirani's book). Your suggestion is still only a $\tfrac12$-approximation in this case (consider a formula where half the variables appear only in clauses where every literal is positive and the rest appear only in clauses where every literal is negative, and half the clauses are all-positive, half all-negative).
> 9 votes

---
Tags: satisfiability, approximation
---


# Question
Title: What is the relation between an algorithm and its implementation at the level of code?
Is there any isomorphism or equivalence relation? What strictly bind these two together?

# Answer
An algorithm is a method for performing some task; an implementation is an expression of that method in a particular language.
> 2 votes

---
Tags: algorithms, formal-languages, turing-machines, programming-languages, semantics
---


title: Idea for a Graph Based Algorithm

text:
# Question
Title: Idea for a Graph Based Algorithm
Assume there is a Shopping Mall x and all the roads in the city are one way such that, irrespective of the path you take starting from x, you will always end up at vertex x. Device an algorithm to test the same.

This seems to be the opposite of a mother vertex, where x is reachable from all vertices instead of all vertices being reachable from x. One way I can think of solving it is to perform DFS on all the vertices and check whether x is visited.

An alternate solution which I'm not very sure of, would be to perform the Kosaraju's strongly connected algorithm and prove that there is only 1 connected component. As the question dictates that irrespective of the path you take, you always end up at x, would mean that every vertex would eventually, connect to a vertex connecting to x followed by x itself.

Is this intuition correct?

# Answer
> 1 votes
You don't mention that visiting a vertex multiple times is not allowed so I will assume that there isn't such a restriction. In your comment on your question you state that:

> The question is on the lines of If I were to start driving from X, no matter how I drive, I **can** always reach x

So the question is if $x$ is reachable from all nodes which are reachable by $x$. This is an easy to solve problem in linear time. First do a dfs from $x$ using the right direction of the edges to find which nodes are reachable by $x$. Let's name this set of nodes $A$. Then do a second dfs from $x$ to find from which nodes you can reach $x$. Let's name this set of nodes $B$. The answer of the problem is positive iff $$A \subseteq B$$ You can check if this condition holds in linear time. The algorithm consists of the following steps:

1. Read input and initialize two adjacency lists (right and reverse edge directions): $O(N + M)$
2. Execute dfs from $x$ using right edge directions and mark visited nodes ($A$): $O(N + M)$
3. Execute dfs from $x$ using reverse edge directions and mark visited nodes ($B$): $O(N + M)$
4. Check whether $A \subseteq B$ or equivalently if $u \in A \Rightarrow u \in B$: $O(N)$

The total computational and space complexity of the above algorithm is $O(N + M)$ (linear), where $N = |V| \wedge M = |E|$. You may check the following C++ code if you want.

```
#include <iostream>
#include <vector>
using namespace std;

#define MAXN 100005  // Maximum number of nodes + 5 (change according to your requirements)

vector<int> E[MAXN];  // Adjacency lists with right edge directions
vector<int> RE[MAXN];  // Adjacency lists with reverse edge directions

bool A[MAXN];  // A[i] will become true iff i-th node is reachable from x
bool B[MAXN];  // B[i] will become true iff x is reachable from i-th node

void dfs(int u)
{
    A[u] = true;  // u was reached from x
    for (int i = 0; i < E[u].size(); i++)  //  for every out-neighbour of u...
    {
        int v = E[u][i];  // We name this node v
        if (!A[v]) dfs(v);  // If you haven't visited v yet, visit it now
    }
}

void dfsr(int u)
{
    B[u] = true;  // x can be reached from u
    for (int i = 0; i < RE[u].size(); i++)  //  for every in-neighbour of u...
    {
        int v = RE[u][i];  // We name this node v
        if (!B[v]) dfsr(v);  // If you haven't visited v yet, visit it now
    }
}

int main()
{
    // Read input and make initializations...
    // I assume that nodes are numbered from 0 to N-1
    int N, M, x;
    cin >> N >> M >> x;
    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;  // There is an edge from u to v
        E[u].push_back(v);  // Right direction from u to v
        RE[v].push_back(u);  // Reverse direction from v to u
    }

    dfs(x);  // DFS from x using the right direction of edges
    dfsr(x);  // DFS from x using the revers direction of edges

    // Check if A is a subset of B (A[x] => B[x])
    for (int i = 0; i < N; i++) if (A[i] && !B[i])
    {
        cout << "NO\n";
        return(0);
    }
    cout << "YES\n";
    return(0);
}

```

I would like to note two facts:

1. In your comment you say that the problem statement is equivalent with wether $x$ is reachable by every node. This is not true based on your previous statement. It asks if $x$ is reachable by every node **reachable by $x$**, which is different. If that was the case only one dfs from $x$ using the reverse edges would be required.
2. On your question you proposed an idea about finding the strongly connected components. It is true that you can answer the question using this technique, but you don't have to find if there is only one strongly connected component (that solves the wrong problem - see 1.). Instead you have to verify that there is no edge from $x$'s strongly connected component to any other strongly connected component (in which case there would be nodes where you could go starting from $x$ but then you could not return to $x$ from them). This is a correct solution for your problem which also has linear time complexity. Although its implementation is a little bit harder and there is no reason to make things more complex than they are.

---
Tags: graphs, graph-traversal
---


# Question
Title: NP-Complete is not closed under kleene star
Consider $\Sigma=\\{0,1\\}$. Suppose that $L \subset \Sigma^\*$ is $NP-$Complete. How can I prove that $L' = L \cup \\{0,1\\}$ is $NP-$Complete?

# Answer
$L$ is $\mathrm{NP}$-complete, so, for any $X\in\mathrm{NP}$, there is a many-one reduction $f\_X$ from $X$ to $L$. Just modify $f\_X$ so that it's a reduction to $L'$ instead. Note that $f\_X$ already does the right thing unless you have some $w$ such that $f\_X(w)\in\\{0,1\\}$.

Note that the same technique shows that $L\cup S$ is still $\mathrm{NP}$-complete for any finite $S\subseteq \Sigma^\*$.
> 1 votes

---
Tags: complexity-theory, computability
---


# Question
Title: What type of operations are seen the most at the physical disk level — reads or writes? Why?
This question came up in my operating systems class in a section about file system cache and RAID.

I'm speculating that the answer is that writes are seen more at the physical disk level because an efficient cache reduces the need to read from the disk.

Can someone confirm or correct this?

# Answer
> 4 votes
The proportion of reads to writes would be workload and system dependent. Before filtering by caching, reads will typically be more common, if for no other reason than code being read-only and data writes being dependent on at least an equal proportion of reads.

Under paging, discarding a clean (stored) page reduces the number of storage accesses, so there is an incentive for the OS to prefer paging out such pages. This biases toward reads (paging-in) at the storage level. (Obviously, allowing dirty pages to accumulate endangers responsiveness since eventually the best page to replace would be dirty so that demand for a not present page would be delayed by the required writeback. Maintaining a modest free list would ameliorate this issue.)

For an in-memory database (with persistence) or a log (or backup) server, writes would presumably dominate. In the former case reads are satisfied by memory *by design*; in the latter case reads are simply less common.

For many tasks oriented toward content consumption such as webserving and gaming where writes are much less common, storage reads can easily dominate even with caching.

Prefetching can also increase the number of read requests. If the cost of a read miss is high and the cost of an unused read is moderate, even somewhat aggressive prefetching can be beneficial.

The relative costs of reads and writes can also be a factor that can bias OS policies with respect to caching/prefetching. SSDs generally provide much higher read bandwidth than write bandwidth and do not penalize random accesses, reducing the cost of prefetching under low memory utilization.

Overprovisioning memory (in terms of cost per unit of work) can reduce the frequency of storage reads (moving toward the in-memory database model) and may be a reasonable design choice due to an impracticality of sharing memory across more work (and the non-linear cost per bit), a preference for responsiveness over average throughput, or a desire for load tolerance (i.e., the extra memory may not be worthwhile for *average* throughput or responsiveness but may avoid issues under high load).

Persistent (battery-backed or inherently persistent) memory can greatly reduce the number of writes to actual storage.

RAID will generally amplify the number of writes but not the number of reads seen by disks (RAID systems typically rely on the disks' internal error detection to detect read errors but write to more than one disk on a write).

# Answer
> 1 votes
Paul Clayton's answer is great. One small claim: in many/most systems there is at least one read for every write. (Otherwise you are writing data that will never be ignored; it will just be effectively thrown away. While that can happen, in many systems it usually doesn't happen too often.) Therefore, in many systems the number of reads is higher than the number of writes. It doesn't always have to be that way -- this is definitely not a hard-and-fast rule, and there are definitely important counter-examples -- it's just something that might often be true.

---
Tags: operating-systems
---


# Question
Title: Does this article imply that Turing-Computability is not the same as "effectively computable"?
I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve. In my understanding, this should mean, intuitively, that this problem is "effectively computable", since we have an effective, real method to compute it: build a quantum computer and solve it. But, since a Turing Machine (turing machines are not quantum computers, I think?) can not solve it, this is not turing-computable.

Hence, does this mean that "effectively computable" and "turing-computable" are not the same concept? So, is the Church-Turing thesis wrong? My intuition says "no", because in that case, this would be very big news. So, if not, why not?

Also, I am aware that there exist already models of computation that are more powerful than turing machines, but those are only "theoretic", aren't they? Quantum computers, on the other hand, could be physically buildable.

# Answer
> 14 votes
There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them with the public key, and for each of them check whether they match the ciphertext. In a purely abstract sense, this is an algorithm that "can" break AES-512. From a practical point of view, converting all the matter in the known universe into computers, and running the program on them until the heat death of the universe, would not be able to check all 2^512 blocks.

Thus, there's an abstract, theoretical concept of "can" that does not take into account the amount of resources required, and a practical meaning that does.

Turing Computability is concerned with the first type of "can". A Turing machine is a device that is allowed to run for unlimited time with unlimited memory. It is an abstract model used to formulate theoretical claims. No true TM actually exists in the real world.

Thus, there is no contradiction between claiming, on the one hand, that anything a quantum computer can do, a TM can also do, and on the other hand claiming that there are problems that a quantum computer can solve, but no classical computer can solve; an actual computer will have computer power restrictions that a TM does not have.

# Answer
> 18 votes
First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.

The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, we want to know more than just whether a problem is computable. Most problems considered by this field are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.

The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.

BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.

This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.

---

As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)

---
Tags: turing-machines, quantum-computing, church-turing-thesis
---


title: Convert FOL clauses to PROLOG

text:
# Question
Title: Convert FOL clauses to PROLOG
I am very new to PROLOG so it might be a very trivial question, but I absolutely have no idea how to solve it. There are 4 sentences I need to formulate into PROLOG code:

> * All hounds howl at night.
> * Anyone who has any cats will not have any mice.
> * Light sleepers do not have anything which howls at night.
> * John has either a cat or a hound.

I convert sentences to well-formed formula in first-order predicate calculus like that

```
- ∀x (HOUND(x) → HOWL(x))

- ∀x ∀y (HAVE(x,y) ∧ CAT (y) → ¬∃z (HAVE(x,z) ∧ MOUSE (z)))

- ∀x (Light_Sleeper(x) → ¬∃y (HAVE (x,y) ∧ HOWL(y)))

- ∃x (HAVE (John,x) ∧ (CAT(x) ∨ HOUND(x)))

```

Now I don't know how to write them in Prolog. Also, how can I make query on them?

# Answer
> 2 votes
If you can convert them to Horn clauses, you can convert them to Prolog.

If you can't convert them to Horn clauses, I don't think you can convert them to Prolog.

So, convert them to Horn clauses first, and then see the answer to this question:

Horn clause to Prolog

---
Tags: first-order-logic, prolog
---


# Question
Title: What is the computation model of Prolog?
Several computation models have representative programming language counterparts, as, according to this answer, Snobol for rewriting systems, APL for combinators, Lisp/Scheme for lambda calculus, and off course the family of imperative languages for TMs (or more precisely RAMs). It seems to me that Prolog should also be a paradigmatic language for some model. Is this assumption true? If so, what is the name of that model?

# Answer
> 2 votes
I think the computation model of Prolog is the SLDNF resolution of Horn clauses.

Prolog is actually very procedural. Kowalski 1974: "The interpretation of predicate logic as a programming language is based upon the interpretation of *implications* \[...\] as *procedure declarations* \[...\]" (emphasis mine)

https://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf

(However, lambda calculus, theorem provers, and Turing machines are term rewriting systems indeed. What is a computational model then, if everything is a term rewriting system?)

---
Tags: computation-models, prolog
---


# Question
Title: How to generate all possible test cases of length $n$ for comparison sorts
Comparison sorts only care about the relative order of elements, not their exact values. So if the relative order of two arrays are the same, a comparison sort algorithm will act the same way on those two arrays.

For example, \[0, 3, 1, 9, 1\] is the same as \[-3, 12, 7, 13, 7\], since their relative orders are the same.

I want to generate all possible test cases of length $n$ for comparison sorts that all possible relative orders are considered, and no two different test cases have the same relative order.

The number of possible test cases of length $n$ is given by A000670.

Here are all possible test cases of length 0:

```
[]

```

Here are all possible test cases of length 1:

```
[0]

```

Here are all possible test cases of length 2:

```
[0, 0]
[0, 1]
[1, 0]

```

Here are all possible test cases of length 3:

```
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[0, 2, 1]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

```

Is there a generic way rather than brutal force to generate these test cases?

# Answer
Yes, there is an algorithm to generate all the possible test cases with length equal to $n$ and only them, significantly faster than the naive brute force algorithm would do.

Firstly, let's sort the numbers of each testcase you provided with length equal to 3 in ascending order and list only the different testcases that we get as result.

```
[0, 0, 0]
[0, 0, 1]
[0, 1, 1]
[0, 1, 2]

```

There are $4 = 2^2 = 2^{3 - 1}$ results. Note that the first value always has to be zero and while we move to the left within a specific testcase we can keep the previous value or increase it by one. So the number of different sorted testcases of length $n$ is $2^{n - 1}$. You can produce these sorted testcases by using a binary array whose value is initially zero and it's increased by one after each step.

After creating the sorted testcases you would like to have all the permutations of each one of them. Note that the number of permutations of a testcase is lower than $n!$ for all testcases except one (the $\[1, 2, 3, \dots, n\]$). Also note that the permutations of the different sorted testcases do not overlap. There is a built-in function in C++ which can create these permutations efficiently, named "next\_permutation". The algorithm used for its implementation is nicely described on a Stack Exchange accepted answer which you can read here: std::next\_permutation Implementation Explanation. I encourage you to read this description of the algorithm.

Bellow I provide you with a C++ implementation of the full algorithm that takes $n$ as input and produces all the different testcases that you want efficiently.

```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 105  // Assumed maximum value of n

int A[MAXN];  // The binary array used to create the sorted testcases
// Initially A is 0 (every number in it is zero)

vector<int> C;
// A vector that stores current sorted testcase and is used to obtain its permutations

int main()
{
    int n;
    cin >> n;  // Read n
    do
    {
        C.clear();  // Clear the vector C to create a new sorted testcase
        int cnt = 0;
        // cnt counts how many times we have increased the number to be inserted in the testcase
        for (int i = 0; i < n; i++)  // Create the sorted testcase of length n number by number
        {
            if (A[i]) cnt++;  // Binary array at current index shows if we should increase the number
            C.push_back(cnt);  // Put the current number in the end of the current sorted testcase
        }

        // Output all permutations of the current testcase
        do
        {
            for (int i = 0; i < n; i++) cout << C[i] << ' ';
            cout << '\n';
        } while (next_permutation(C.begin(), C.begin() + n));  // Continue while there are unprinted permutations

        // Increase binary array by one
        A[n - 1]++;  // We add one at the position n - 1 (least significant bit)
        int p = n - 1;
        while (p && A[p] == 2)  // We move the carry from right to left
        {
            A[p] = 0;
            A[--p]++;
        }
    } while (!A[0]);  // First number of sorted testcase must be 0, so when it becomes 1 we have finished
    return(0);
}

```
> 1 votes

---
Tags: algorithms
---


# Question
Title: Priority queue with a buffer for delayed insertion and other tweaks
I was thinking of ways to optimise a (heap-based) priority queue in certain scenarios, like in best-first path search algorithms (Dijkstra, A\*, etc.).

One possible optimisation is to delay insertions until the next extraction. The inserted elements can be kept in a buffer (a simple stack) until the next extractions, and then inserted with some kind of optimised "bulk insertion" method.

Another possible tweak is to check if the element to be inserted has a higher priority than all the waiting ones, and if so, to store it in a second stack, which is to be used for the subsequent extraction. If the priority of the element to be inserted is not the highest but higher than the priorities of all the elements in the heap, then the elements from the second stack can replace the elements at the top of the heap, while the replaced elements are moved to the buffer for delayed insertion. This tweak however would add a noticeable overhead, so it is not clear if it would be an optimisation in any scenario.

Has such or similar modifications of (heap-based) priority queues been studied or used in practice?

# Answer
> 2 votes
There are several approaches that combine multiple buckets and heaps to improve shortest path algorithms. At good starting point would be Dial's algorithm or Cherkassky, Goldberg & Silverstein.

---
Tags: algorithms, data-structures, heaps, priority-queues
---


# Question
Title: Hungarian Algorithm - Bipartite Graph Approach
I have been having some difficulty making sense of the Hungarian Algorithm outlined here. It seems incomplete and/or erroneous to me. The main issue is the line:

> If R\_T ^ Z is nonempty, then reverse the orientation of a directed path in...

How do we know which path to select as "a path"? If we select the wrong path, how do we recover? This seems to be a monotonically assigning algorithm, in that we can only ever create new assignments, but never remove or alter existing ones.

Suppose we have a simple example of S = {A, B}, T = {W, X} with weights AW: 2, AX: 2, BW: 6, BX: 4. How do we select whether to add AW or AX to the mapping first, or how to we recover from making the wrong selection?

# Answer
> 2 votes
(Converting a comment into a proper answer. Note that I now use the minimum cost convention of the reference given in the question.)

Any augmenting path serves. Note that you reverse the order of the arcs. Say you choose AW of cost -2 first. Then you have forward arcs AX, BW, BX, and backward arc WA, which has been reversed. Now BW,WA,AX is an augmenting path, of cost -6+2-2=-6, and you end up with backward arcs WB,XA which represent the optimal solution 8.

---
Tags: algorithms, graphs, bipartite-matching
---


# Question
Title: Complexity of union-find with path-compression, without rank
Wikipedia says union by rank without path compression gives an amortized time complexity of $O(\log n)$, and that both union by rank and path compression gives an amortized time complexity of $O(\alpha(n))$ (where $\alpha$ is the inverse of the Ackerman function). However, it does not mention the running time of path compression without union rank, which is what I usually implement myself.

What's the amortized time complexity of union-find with the path-compression optimization, but without the union by rank optimization?

# Answer
Seidel and Sharir proved in 2005 \[1\] that using path compression with arbitrary linking roughly on $m$ operations has a complexity of roughly $O((m+n)\log(n))$.

See \[1\], Section 3 (Arbitrary Linking): Let $f(m,n)$ denote the runtime of union-find with $m$ operations and $n$ elements. They proved the following:

> **Claim 3.1.** For any integer $k\>1$ we have $f(m, n)\leq (m+(k−1)n)\lceil \log\_k(n) \rceil$.

According to \[1\], setting $k = \lceil m/n \rceil + 1$ gives $$f(m, n)\leq (2m+n) \log\_{\lceil m/n\rceil +1}n$$.

A similar bound was given using a more complex method by Tarjan and van Leeuwen in \[2\], Section 3:

> **Lemma 7 of \[2\].** Suppose $m \geq n$. In any sequence of set operations implemented using any form of compaction and naive linking, the total number of nodes on find paths is at most $(4m + n) \lceil \log\_{\lfloor 1 + m/n \rfloor}n \rceil$ With halving and naive linking, the total number of nodes on find paths is at most $ (8m+2n)\lceil \log\_{\lfloor 1 + m/n \rfloor} (n) \rceil $.
>
> **Lemma 9 of \[2\].** Suppose $m \< n$. In any sequence of set operations implemented using compression and naive linking, the total number of nodes on find paths is at most $ n + 2m \lceil \log n\rceil + m$.

\[1\]: R. Seidel and M. Sharir. Top-Down Analysis of Path Compression. Siam J. Computing, 2005, Vol. 34, No. 3, pp. 515-525.

\[2\]: R. Tarjan and J. van Leeuwen. Worst-case Analysis of Set Union Algorithms. J. ACM, Vol. 31, No. 2, April 1984, pp. 245-281.
> 8 votes

# Answer
I don't know what the amortized running time is, but I can cite one possible reason why in some situations you might want to use both rather than just path compression: the worst-case running time per operation is $\Theta(n)$ if you use just path compression, which is much larger than if you use both union by rank and path compression.

Consider a sequence of $n$ Union operations maliciously chosen to yield a tree of depth $n-1$ (it is just a sequential path of nodes, where each node is the child of the previous node). Then performing a single Find operation on the deepest node takes $\Theta(n)$ time. Thus, the worst-case running time per operation is $\Theta(n)$.

In contrast, with the union-by-rank optimization, the worst-case running time per operation is $O(\log n)$: no single operation can ever take longer than $O(\log n)$. For many applications, this won't matter: only the total running time of all operations (i.e., the amortized running time) will matter, not the worst-case time for a single operation. However, in some cases the worst-case time per operation might matter: for instance, reducing the worst-case time per operation to $O(\log n)$ might be useful in an interactive application where you want to make sure that no single operation can cause a long delay (e.g., you want a guarantee that no single operation can cause the application to freeze for a long time) or in a real-time application where you want to ensure that you will always meet the real-time guarantees.
> 6 votes

---
Tags: complexity-theory, time-complexity, union-find
---


# Question
Title: Polygon casting - Removing from mold by rotation
The following question appears in Section 4.9 of "Computational Geometry: Algorithms and Applications" By Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf:

> Show that the problem of finding a center of rotation that allows us to remove $P$ with a single rotation from its mold can be reduced to the problem of finding a point in the common intersection of a set of half-planes.

$P$ here is a simple polygon with a given orientation, cast in a mold -

Whether $P$ can be removed with a translation can be reduced to whether a common intersection of a set of half-planes is unbounded: Each edge of $P$, continued to a line, defines the half plane touching the outer side of the edge. The intersection of these half-planes is unbounded in a direction $\vec{v}$ if and only if translating $P$ by $\vec{v}$ does not cause any edge to push against the mold.

How can this reduction be modified to solve the case of removing $P$ with a rotation around a point?

# Answer
Consider the marked edge of the following object (light gray) in its mold (dark gray) -

Where must $p$ be such that an arbitrary points on the edge will not be pushed against the mold? This figure shows the direction a point on the edge will be moving in when rotated around a point $p$ \-

Notice that the point will be moving perpendicular to the line connecting it with $p$. Now recall that in order not to push on the mold, the points of the edge must move in the direction of the inner half-plane defined by the edge. This means that the possible locations for $p$ lie on a half-plane perpendicular to the edge. Here's the half-plane (in green) corresponding to an inner point of the edge -

The half-plane corresponding to the upper vertex of the edge, in this case, is contained in all of the half-planes for inner points, and so a rotation around any point in it moves the entire edge such that it does not push on the mold.

Whether $P$ can be removed with a rotation around $p$, is thus equivalent to whether $p$ is in the common intersection of the half-planes defined by $P$'s edges.
> 4 votes

---
Tags: algorithms, reductions, computational-geometry
---


# Question
Title: Which time series prediction techniques are useful given harmonic properties?
I have a time series dataset where events have harmonic properties, and seemingly the nature of the event's early segments can determine the remainder of the event (see example 1's oscillations). Additionally, these early segments might determine the properties/likelihood of some following/associated event (example 2).

Which time series prediction techniques may be suitable for making predictions based on this kind of behaviour? Specifically:

1. For determining how an event, from appearance, might oscillate and dissipate (forecast/extrapolation).
2. For predicting what event may follow (probabilistic model).

I am not very knowledgeable in this, but seemingly dynamic ARIMA may be appropriate for the extrapolation at a given point. Also, the early segment might be suitable as a feature for prediction in some other model (e.g. SVC)?

Example Event 1

Example Event 2

---

**EDIT**: I want to avoid fitting a highly specialised/targeted model based on observation - but would be happy for some process to learn this representation. I am interested in learning about existing models/methodologies that could be applied to this problem, references would be great.

# Answer
> 1 votes
I would suggest to make the correlation plot and observe the dependencies. Yes, ARIMA, is so far the best forecasting model for time series and it should work in this data set too. For the implementation, in R, there is auto ARIMA, which automatically takes the best suited valued for the parameters( p: The number of lag observations included in the model, also called the lag order. d: The number of times that the raw observations are differenced, also called the degree of differencing. q: The size of the moving average window, also called the order of moving average.)

But as far as I am concerned, in Python, you have to manually tune the parameters by yourself by analyzing the correlation plot. This is a very well explained beginner level tutorial for the implementation in Python.
Let me know in the comments if it works (or not).

---
Tags: machine-learning, reference-request, pattern-recognition, time-series-analysis
---