Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of free memory required to hold the working data. This is in contrast to algorithms that are compute-bound, 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 tables.
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 technique called memoization in order to relieve the inefficiency of recursion 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 that computes the Fibonacci numbers. The following pseudocode uses recursion and memoization, and runs in linear CPU time: Fibonacci (n) { for i = 0 to n-1 results[i] = -1 // -1 means undefined
return Fibonacci_Results (results, n); }
Fibonacci_Results (results, n) { if (results[n] != -1) // If it has been solved before, return results[n] // look it up. if (n == 0) val = 0 else if (n == 1) val = 1 else val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1) results[n] = val // Save this result for re-use.
return val
}
Compare the above to an algorithm that uses only recursion, and runs in exponential CPU time: Recursive_Fibonacci (n) { if (n == 0) return 0 if (n == 1) return 1
return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2) } 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 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 that could deter spam, which has become a problem of epidemic proportions on the Internet.
In 1992, IBM research scientists Cynthia Dwork and Moni Naor published a paper at CRYPTO 1992 titled Pricing via Processing or Junk Mail, suggesting a possibility of using CPU-bound 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 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.