I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as RAM. The assumption is that the primary storage already has the capacity to store and address the input, so it should be feasible to expect rapid performance on the words that encode the address space. This is reasonable, yet I think that the model may give equal footing to algorithms that perform inherently different amounts of work - such as returning a constant and mapping numbers (the latter is obviously more demanding in a non-Neumann architecture). Similarly, on a tangent topic, the development of parallel algorithms assumes infinitely parallel hardware, which does not take into account the spatial factors involved in a circuit design.
Furthermore, while contemporary machines provide integer-based addressing and while I see this as an arbitrary beneficial phenomenon, I don't think that there is fundamental need for our addresses to be effective quantities, with the corresponding constant-time arithmetic operations on them. So this may also influence the analysis of algorithms towards disbalance.
In view of the above, I have the following questions:
- Are there operations, to our understanding, that we expect to be implemented efficiently in our fully featured (i.e. for practical evaluation) models of computation and why - arithmetic, or any polylogarithmic complexity operation (assuming the standard encodings), or any function that maps words, even finding the n-th prime number if it fits in a word. Why we choose particular operations, and could we choose others? Can we use a different encoding, not based on positional numerals as the medium of computation and gain some comparative benefits throughout?
- Is it conceivable that data structures and algorithms may be improved asymptotically if they were implemented directly as VLSI circuit designs? For example, is it theoretically conceivable that sorting and dynamic indexing (single-, multi-dimensional) of sets with variably-sized lexicographically ordered keys can be implemented more efficiently if we don't use RAM as our point of reference? Is there counterproof to that, proof, or conjecture?
- If improvements appear to be possible under 2, how the relationship between the model and the problem enable such improvements? For example, given a universe of keys for an indexing problem, how can we decide if a given model of computation (restricted by faithful correspondence to the VLSI design economics) is optimal, or a better model of computation exists (again feasible and faithful to VLSI economics, but different operations and implementation)?
PS: A similar issue with lock-free algorithms in my opinion is that they assume the underlying architecture provides atomic operations that scale perfectly with the number of cores and cpus. The interconnects and coherency protocols can not scale perfectly, so essentially the algorithms remain blocking. The algorithmic design optimally solves the problem with the resources provided by the model, but this does not answer which is the most optimal practically feasible hardware architecture for solving the original problem, and whether from this point of view the algorithm is actually optimal.