9
$\begingroup$

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:

  1. 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?
  2. 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?
  3. 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)?

Thanks

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.

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ These are good questions, but difficult to answer quickly. In short, (1) encoding matters and can make a huge difference, especially if you assume certain operations are "cheap" (2) changing the model of computation can definitely improve things asymptotically (like from one poly to a smaller poly) (3) we see this in sorting, where in a comparison model n log n operations are needed, but in a RAM model you can get around this. $\endgroup$
    – Suresh Venkat
    Dec 14, 2013 at 19:30
  • $\begingroup$ @Suresh The comparison model is very abstract. Essentially, I wonder if there are circuit design schemata that respect real-world issues like space constraints and such, that can provide solutions to specific problems that outperform asymptotically their RAM-optimized counterparts running on optimal circuit implementation of a RAM machine. I ask of the kind of design choices could result in such performance benefits - like encodings, instruction set, etc. and how a suboptimal for a problem model can be recognized without trying all possible model VLSI implementation-solution configurations. $\endgroup$
    – simeonz
    Dec 14, 2013 at 21:19
  • 1
    $\begingroup$ simeonz: It is widely (universally?) believed that no hardware improvement will result a polynomial-time solution to a problem that was previously only implementable in exponential time. The caveats to that statement are quantum computing and massive parallelization (i.e. parallelization that grows with the size of the input). However, differences in polynomials (like $n^3$ to $n^2$) can definitely be hardware-model-dependent. $\endgroup$
    – usul
    Dec 15, 2013 at 2:05
  • $\begingroup$ @usul So you are saying that it is theoretically conceivable that changing the circuit implementation from RAM-like to something else can enable improvements in the asymptotic performance? Can someone provide any references or a field of tcs that deals with this particular aspect formally. I am not theoretically savvy enough to guess it. (Preferably the changes should not arbitrarily increase the size of the circuit, but any theoretic treatment would be great.) $\endgroup$
    – simeonz
    Dec 15, 2013 at 6:47
  • 1
    $\begingroup$ some of this relates to the "uniform vs nonuniform" question in circuits [mostly open]... you might also look into "cache oblivious algorithms" for another theoretical take on it all. related, there is also an old paper by ? that shows that factoring can be done in polynomial number of arithmetic operations, but with large numbers. [does anyone recall that ref?] $\endgroup$
    – vzn
    Dec 16, 2013 at 1:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.