Memory bound refers to a situation in which the time to complete a given
computational problem
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computational probl ...
is decided primarily by the amount of free
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
required to hold the working
data
In the pursuit of knowledge, data (; ) is a collection of discrete values that convey information, describing quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted ...
. This is in contrast to algorithms that are
compute-bound
{{Unreferenced, date=April 2007
In computer science, a computer is CPU-bound (or compute-bound) when the time for it to complete a task is determined principally by the speed of the Central processing unit, central processor: processor utilization ...
, where the number of elementary computation steps is the deciding factor.
Memory and computation boundaries can sometimes be traded against each other, e.g. by saving and reusing preliminary results or using
lookup table
In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from hash tables in a way that, to retrieve a value v wi ...
s.
Memory-bound functions and memory functions
Memory-bound
functions and memory functions are related in that both involve extensive memory access, but a distinction exists between the two.
Memory functions use a
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
technique called
memoization
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization ...
in order to relieve the inefficiency of
recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
that might occur. It is based on the simple idea of calculating and storing solutions to subproblems so that the solutions can be reused later without recalculating the
subproblems again. The best known example that takes advantage of memoization is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
that computes the
Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s. The following
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
uses recursion and memoization, and runs in
linear CPU time:
Fibonacci (n)
Fibonacci_Results (results, n)
Compare the above to an algorithm that uses only recursion, and runs in
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
CPU time:
Recursive_Fibonacci (n)
While the recursive-only algorithm is simpler and more elegant than the algorithm that uses recursion and memoization, the latter has a significantly lower
time complexity
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
than the former.
The term "memory-bound function" has surfaced only recently and is used principally to describe a function that uses XOR and consists of a series of computations in which each computation depends on the previous computation. Whereas memory functions have long been an important actor in improving time complexity, memory-bound functions have seen far fewer applications. Recently, however, scientists have proposed a method using memory-bound functions as a means to discourage spammers from abusing resources, which could be a major breakthrough in that area.
Using memory-bound functions to prevent spam
Memory-bound functions might be useful in a
proof-of-work system
Proof of work (PoW) is a form of cryptographic proof in which one party (the ''prover'') proves to others (the ''verifiers'') that a certain amount of a specific computational effort has been expended. Verifiers can subsequently confirm this exp ...
that could deter
spam
Spam may refer to:
* Spam (food), a canned pork meat product
* Spamming, unsolicited or undesired electronic messages
** Email spam, unsolicited, undesired, or illegal email messages
** Messaging spam, spam targeting users of instant messaging ( ...
, which has become a problem of epidemic proportions on the
Internet
The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...
.
In 1992, IBM research scientists
Cynthia Dwork
Cynthia Dwork (born June 27, 1958) is an American computer scientist at Harvard University, where she is Gordon McKay Professor of Computer Science, Radcliffe Alumnae Professor at the Radcliffe Institute for Advanced Study, and Affiliated Professo ...
and
Moni Naor
Moni Naor ( he, מוני נאור) is an Israeli
Israeli may refer to:
* Something of, from, or related to the State of Israel
* Israelis, citizens or permanent residents of the State of Israel
* Modern Hebrew, a language
* ''Israeli'' (news ...
published a paper at CRYPTO 1992 titled ''Pricing via Processing or Junk Mail'',
updated version of same
suggesting a possibility of using
CPU-bound
{{Unreferenced, date=April 2007
In computer science, a computer is CPU-bound (or compute-bound) when the time for it to complete a task is determined principally by the speed of the central processor: processor utilization is high, perhaps at 100% ...
functions to deter abusers from sending spam. The scheme was based on the idea that computer users are much more likely to abuse a resource if the cost of abusing the resource is negligible: the underlying reason spam has become so rampant is that sending an
e-mail
Electronic mail (email or e-mail) is a method of exchanging messages ("mail") between people using electronic devices. Email was thus conceived as the electronic ( digital) version of, or counterpart to, mail, at a time when "mail" meant ...
has minuscule cost for spammers.
Dwork and Naor proposed that spamming might be reduced by injecting an additional cost in the form of an expensive
CPU computation: CPU-bound functions would consume CPU resources at the sender's machine for each message, thus preventing huge amounts of spam from being sent in a short period.
The basic scheme that protects against abuses is as follows:
Let be sender, be recipient, and be an e-mail. If has agreed beforehand to receive e-mail from , then is transmitted in the usual way. Otherwise, computes some function and sends to . checks if what it receives from is of the form . If yes, accepts . Otherwise, rejects .
The figure on the right depicts cases in which there were no prior agreements.
The function is selected such that the verification by is relatively fast (taking a millisecond) and such that the computation by is somewhat slow (involving at least several seconds). Therefore, will be discouraged from sending to multiple recipients with no prior agreements: the cost in terms of both time and computing resources of computing repeatedly will become very prohibitive for a spammer who intends to send many millions of e-mails.
The major problem of using the above scheme is that fast CPUs compute much faster than slow CPUs. Further, higher-end computer systems also have sophisticated pipelines and other advantageous features that facilitate computations. As a result, a spammer with a state-of-the-art system will hardly be affected by such deterrence while a typical user with a mediocre system will be adversely affected. If a computation takes a few seconds on a new
PC, it may take a minute on an old PC, and several minutes on a
PDA
PDA may refer to:
Science and technology
* Patron-driven acquisition, a mechanism for libraries to purchase books
*Personal digital assistant, a mobile device
* Photodiode array, a type of detector
* Polydiacetylenes, a family of conducting poly ...
, which might be a nuisance for users of old PCs, but probably unacceptable for users of PDAs. The disparity in client CPU speed constitutes one of the prominent roadblocks to widespread adoption of any scheme based on a CPU-bound function. Therefore, researchers are concerned with finding functions that most computer systems will evaluate at about the same speed, so that high-end systems might evaluate these functions somewhat faster than low-end systems (2–10 times faster, but not 10–100 times faster) as CPU disparities might imply. These ratios are "
egalitarian
Egalitarianism (), or equalitarianism, is a school of thought within political philosophy that builds from the concept of social equality, prioritizing it for all people. Egalitarian doctrines are generally characterized by the idea that all hum ...
" enough for the intended applications: the functions are effective in discouraging abuses and do not add a prohibitive delay on legitimate interactions, across a wide range of systems.
The new egalitarian approach is to rely on memory-bound functions. As stated before, a memory-bound function is a function whose computation time is dominated by the time spent accessing memory. A memory-bound function accesses locations in a large region of memory in an unpredictable way, in such a way that using caches are not effective. In recent years, the speed of CPU has grown drastically, but there has been comparatively small progress in developing faster main memory. Since the
ratio
In mathematics, a ratio shows how many times one number contains another. For example, if there are eight oranges and six lemons in a bowl of fruit, then the ratio of oranges to lemons is eight to six (that is, 8:6, which is equivalent to the ...
s of
memory latencies of machines built in the last five years is typically no greater than two, and almost always less than four, the memory-bound function will be egalitarian to most systems for the foreseeable future.
See also
*
Computer architecture
In computer engineering, computer architecture is a description of the structure of a computer system made from component parts. It can sometimes be a high-level description that ignores details of the implementation. At a more detailed level, t ...
*
CPU-bound
{{Unreferenced, date=April 2007
In computer science, a computer is CPU-bound (or compute-bound) when the time for it to complete a task is determined principally by the speed of the central processor: processor utilization is high, perhaps at 100% ...
*
Dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
*
I/O-bound
In computer science, I/O bound refers to a condition in which the time it takes to complete a computation is determined principally by the period spent waiting for input/output operations to be completed. This is the opposite of a task being CPU bo ...
*
Memoization
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization ...
*
Memory-hard function
In cryptography, a memory-hard function (MHF) is a function that costs a significant amount of memory to evaluate. It differs from a memory-bound function, which incurs cost by slowing down computation through memory latency. MHFs can be used as ...
*
Optimal substructure
In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.{{cite boo ...
*
Proof of work
Proof of work (PoW) is a form of Cryptography, cryptographic proof (truth), proof in which one party (the ''prover'') proves to others (the ''verifiers'') that a certain amount of a specific computational effort has been expended. Verifiers can s ...
*
Recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
*
Memory bottleneck
Random-access memory (RAM; ) is a form of computer memory that can be read and changed in any order, typically used to store working data and machine code. A random-access memory device allows data items to be read or written in almost the s ...
References
*Abadi, M., Burrows, M., Manasse, M., & Wobber, T. (2005, May)
Moderately Hard, Memory-bound Functions ''ACM Transactions on Internet Technology''.
*Dwork, C., Goldberg, A., & Naor, M. (2003)
On Memory-Bound Functions for Fighting Spam ''Advances in Cryptology''.
*Hellman, M. E. (1980)
A Cryptanalytic Time-Memory Trade Off ''IEEE Transactionson Information Theory''.
{{Refend
External links
Implementation of a Memory Bound functionSpam – FTC Consumer Information
Analysis of algorithms
Computer memory
Anti-spam