I read somewhere (forgot which book it is) that algorithms are independent of computer architectures. Some even say algorithms are themselves computation (machines?)?
On the other hand, books on parallel programming have chapters on parallel algorithms. It seems like parallel algorithms depend on parallel architectures?
I think I miss some big pictures? Thanks.
Algorithms are the series of steps taken to solve a particular problem. The recipe for solving the problem, if you will. "Programs" do the same things, of course; we use "algorithm" to suggest the "generalized" or "generally applicable" recipes that are independent of specific machine designs, programming languages, and such.
Algorithms are meant to be general, but they can still depend on some features being present. "Concurrent algorithms," for example, might depend on you having some mechanism for different programs to run concurrently. "Distributed algorithms" can depend on you having more than one system in a cooperating group, and a network or other communication scheme between them. Similarly, "parallel algorithms" are often those designed to run when you have multiple processing units--potentially many, many processing units, and the sort of communication facilities that are common when you have large arrays of processing units. You may be able to run a "parallel algorithm" even when you have only one computer or one CPU--but it's not terribly interesting in the way having traffic engineers isn't very useful unless you also have roads.
Algorithms are independent of computer architecture. That's because algorithms define a series of processes that solves a problem. Regardless of architectures, sorting algorithms will always sort. It wouldn't suddenly render 3D drawings on some architectures.
If you think about it, this is actually intuitive. Google Chrome (which is merely a collection of algorithms) is a web browser when compiled for any architecture. It wouldn't suddenly become a device driver on some architectures.
But the speed with which algorithms runs depends on architectures. And some algorithms work faster than others depending on architectures.
If you think about it, this is also actually intuitive. Given an algorithm, it's always possible for the hardware designer to design an architecture that specifically speeds up that algorithm. That's one reason why there are things like 3D accelerated graphics cards and bitcoin miner accelerators.
When people talk about parallel algorithms, they're talking about a family of algorithms that can work faster on parallel architectures. There are plenty of algorithms that aren't improved by parallel architectures. So identifying new algorithms for the same problem that work well in parallel is an active area of research.
But those algorithms still do the same things. Architectures don't change what they do.
"It seems like parallel algorithms depend on parallel architectures?"
In my opinion the answer is simply: no. General I only get the properties
when thinking of hardware architecture.
Referring to parallelism you can have any parallel algorithm be batch computed and any parallel arch to work serial so the algorithm does not depend on that. Word size might be an issue to numeric stability but not to the algorithm itself. Resource limits like 64bit can only describe 2^64 different numbers could be a problem, but anyway elements are limited.
Of course there might be some algorithms which are depending on some extended instruction sets, but at least everything can be described with basic math.
For example with quantum computing some Big-O values may change and then I would say that
"algorithms are independent of computer architectures"
is not true anymore.
Algorithms doesn't depend on computer architecture, however the efficiency of running any particular algorithm does depend on the architecture. Any Turing Complete machines can emulate any other Turing Complete machines, although some machines would be better at one thing than others.
What we mean by concurrent algorithms is that the algorithm plays well or can take advantage of concurrency in the machine, maybe because it requires less locking that otherwise would have been required by algorithms that aren't specifically designed for the concurrent machine or maybe because the algorithm makes use of divide and conquer effectively to use the full power of the machine. Running the algorithm in a non concurrent machine would still be possible but may not be as efficient or it may require additional locking to perform correctly.
There are also algorithms that are designed to take advantage of the quirk of a particular architecture, like cache-friendly algorithms, which optimises caching. These algorithms may be less efficient in machines that doesn't cache the way the algorithm assumes.
In theory, algorithms are entirely independent of architecture. You can always emulate a parallel architecture on a single-issue timesliced system. You can reason about algorithms without an architecture at all. Knuth's book uses a fictional architecture.
In practice there are algorithms that attempt to achieve better runtime for the same "O" complexity by optimizing the use of cache hardware and synchronisation primitives.
Yes and no. It depends on the constraints you want to meet and the preconditions needed to run your algorithm.
Ideally, an algorithm is an abstract recipe that defines step-by-step how to do something. Algorithms was defined like so with the goal of reproducibility, and later automatization. Algorithms originates from lambda-calcul, so you can easily see why they are made in such a way. This definition is the usual one, but modern algorithms can be non-sequential (not step-by-step, like concurrent algorithms, or logical ones like the ones using unification), non-linear (stochastic algorithms) or just plainly weird (quantum algorithms), but I'll pass that.
Thus, ideally, an algorithm should be as abstract as possible without accounting any hardware.
But, as with any system, you must define some axioms, not only to get a coherent system, but also to gain time. For instance, most algorithms presume, at the very least implicitly, that they are defined on a Von-Neumann machine. If that was not the case, they would need to explicitly define each parts of the system they need to be run on (since this is required to reproduce the recipe, this a kind of precondition). Also, often algorithms relies on common commands such as write() without defining them fully.
Another reason why algorithms are not so abstract from hardware architecture, is when you need to meet some constraints.
Let's say you are working on embedded systems, then probably you can't rely on the same amount of resources you have on workstations. One of the most restrained resources is probably memory. However, most algorithms tend to optimize the time complexity (speed of execution on CPU), not the memory complexity (amount of memory necessary to work on the data). For these systems, memory optimized algorithms have been devised where non memory optimized algorithms would just fail or run a lot slower. In fact, embedded systems are not the sole target of memory efficient algorithms: for example, there are cache-oblivious algorithms that adapts their processing to efficiently use the CPU cache. Another example: some machine learning algorithms for big data are tailored for incremental learning or out-of-core computing to process huge amount of data far bigger than memory available on any computer, etc.
There are also algorithms that do not optimize a specific part of the computer, but a standard that is dependent on hardware architecture. For example, numerical data that need precision are stored inside float or double, which are by nature limited due to hardware limits. The problem is that complex computations can lead to rounding, and the more calculations you do over rounded numbers, the more you will drift off. This is called a catastrophic interference. Some applications need a critical precision, even at the cost of some worst complexity. For this type of applications, algorithms that optimize their calculation to reduce or remove catastrophic interference were made.
Thus, designing an algorithm can also be a trade-off between abstraction and constraints.
In the end, we can say that an algorithm is as abstract as its target is, and as its preconditional (architecture) needs. The more specific target your algorithm aims, the more it will probably rely on the hardware architecture.
Some related keywords that may interest you:
You shouldn't confuse an algorithm in general with mathematical or computing algorithms. If you mean computing algorithms, yes, they are independent from the machine architecture.
Definition of algorithm from Wikipedia:
In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning.
This definition is used to refer some closed computation or data processing tasks. In the other words, computations which can abstractly be run on Turing Machine. However, recently there is a concept in mathematics named Interactive computation that involves input/output communication with the external world during computation.
In a general definition, the algorithm is just a recipe (sequence of instructions). I think you can't think of an algorithm without knowing the instruction set or operations which you can use; Mathematical operations are about calculation, then an algorithm which includes an step named 'heat up the oven' is not a mathematical algorithm but you can give it to a chef, because he knows how to execute it.
Then, you can create a machine which can do X, Y, Z.... each of these could be used in your algorithm as an instruction. But if they are all about closed computation (in fact, non-interactive deterministic digital small-step computations), then one can prove that your machine is equivalent to Turing Machine. But if you target other type of computations (continues values or interactive computation [however I am not sure if they are really another type of computation]) or even none-computing tasks, you can think of machines which can perform them.
This question and answer is also interesting to get a broader perspective on algorithms.
In general, algorithms are designed to some particular problems at while minimizing some measure of "cost". Historically, many algorithms were designed on the assumption that the relative costs of common operations would be relatively similar on many architectures, and thus some typical machines would run one algorithm would run better than another, then on most typical machines the former algorithm would, at worst, be only slightly inferior to the latter. As time has gone by, such an assumption doesn't hold as well as it used to.
For example, it used to be that the number of times a program needed to read things from memory was considered more important than the locations of things to be read. Reading things that were located near each other in memory was somewhat cheaper than reading things that were far apart, but not outrageously show. As main-CPU speeds have increased at a rate far in excess of memory speeds, however, the importance of access sequence has significantly increased. It's possible to have one program execute ten times as many instructions as another and yet still run faster, if the 95% of the former program's memory fetches generate L1 cache hits and a majority of the latter program's memory fetches generate cache misses.
Additionally, certain kinds of concurrency-related algorithms make various assumptions about when data written to memory by one processor core will be "seen" by other cores. Many processors have various ways that they can read and write memory, with varying costs and guarantees about visibility. Some algorithms will work very well on architectures that can satisfy visibility requirements "for free", but poorly on others where the instructions necessary for those guarantees are expensive. Indeed, on some architectures certain concurrency-related algorithms could only be guaranteed to work by limiting execution to a single time-shared CPU core (which would of course defeat the point of using a concurrent algorithm).
A lot of answers are missing the fact that an algorithm can be defined in terms that are either abstract from or in direct, literal relation to an architecture. An algorithm has to be unambiguous, but there's still room for it to be more or less specific.
An algorithm for converting a string to all-caps can be easily described in pseudocode that is architecture-independent. But at the same time, nothing is stopping you from describing an algorithm for converting a string to all-caps specifically on an x86 architecture. All it takes is a x86 Assembly homework assignment. (You can still do this in pseudocode - just pseudocode relating to that architecture!) Just the fact that the problem is specifically for doing this on an x86 architecture doesn't mean you no longer have an algorithm to solve it.
It depends on the problem the algorithm is defined to solve. The algorithm is architecture-independent if the problem it solves is architecture-independent (and assuming that this isn't undone by the way the algorithm is described or put together). The problem can be either a theoretical, blackboard one, or it can be in terms of a very specific architecture. In the latter case, the algorithm, in turn, would be limited to working with that architecture.
Algorithms are a sequence of steps. They don't depend on what is (or isn't) executing them.
However, the time complexity of an algorithm can depend on what is executing it. That's why detailed analysis of an algorithm requires a "model of computation", such as a random-access machine.
Whether or not memory is randomly accessible certainly affects how long your algorithm takes to run, and most algorithms assume this is the case whereas in reality most architectures don't satisfy this condition.
They differs on different context of the problems. Algorithm is the collection of steps to solve a problem. The context of this problem can be theoretically anything. Hence the algorithm of solving the problem can be dependent to literally anything on the universe we can imagine. Let me clarify with an example. Let's say you are given a task to,
Construct an algorithm that will distribute the loads to multiple core when multicore available.
Now can you imagine your algorithm will be dependent to the architecture or not? Of course yes.
