|
Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of available memory to hold data. In other words, the limiting factor of solving a given problem is the memory access speed. The application of memory bound functions could prove to be valuable in preventing spam, which has become a problem of epidemic proportions on the Internet. In theoretical computer science, a computational problem is a mathematical object representing a question that computers might want to solve. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
Data is the plural of datum. ...
In computer science, a subroutine (function, method, procedure, or subprogram) is a portion of code within a larger program, which performs a specific task and is relatively independent of the remaining code. ...
A KMail folder full of spam emails collected over a few days. ...
Memory bound functions and memory functions
Memory bound functions and memory functions are related in that both involve extensive memory access, but a distinction should be made between them
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 pseudo-code illustrates an algorithm that uses memoization, which runs in linear CPU time: In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ...
Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ...
A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ...
Figure 1. ...
Flowcharts are often used to represent algorithms. ...
In mathematics, the Fibonacci numbers, named after Leonardo of Pisa, known as Fibonacci, form a sequence defined recursively by: In other words, each number is the sum of the two numbers before it. ...
Pseudocode is a generic way of describing an algorithm without use of any specific programming language syntax. ...
The word linear comes from the Latin word linearis, which means created by lines. ...
for i = 0 to n-1 result[i] = -1 // -1 means undefined Fibonacci (results, n) { if (results[n] != -1) //check if it has already been solved before return results[n] 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 return val } Compare the above to an algorithm that uses recursion, which runs in exponential CPU time: In complexity theory, exponential time is the computation time of a problem where the time, m(n), is bounded by an exponential function of the problem size, n. ...
Recursive_Fibonacci (n) { if (n == 0) return 0 else if ( n == 1) return 1 else return Recursive_Fibonacci (n -1) + Recursive_Fibonacci (n -2) } While the recursive algorithm is simpler and more elegant than the algorithm that uses 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. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
Using memory bound functions to prevent spam In 1992, IBM research scientists Cynthia Dwork and Moni Naor published a paper titled Pricing via Processing or Combating 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. CPU bound refers to a condition where the time to complete a computation is determined principally by the speed of the central processor and main memory. ...
Wikipedia does not yet have an article with this exact name. ...
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: CPU can stand for: in computing: Central processing unit in journalism: Commonwealth Press Union in law enforcement: Crime prevention unit in software: Critical patch update, a type of software patch distributed by Oracle Corporation in Macleans College is often known as Ash Lim. ...
Let S be sender, R be recipient, and M be an e-mail. If R has agreed beforehand to receive e-mail from S, then M is transmitted in the usual way. Otherwise, S computes some function G(M) and sends (M, G(M)) to R. R checks if what it receives from S is of the form (M, G(M)). If yes, R accepts M. Otherwise, R rejects M. The figure on the right depicts cases in which there were no prior agreements:
The function G() is selected such that the verification by R is relatively fast (taking a millisecond) and such that the computation by S is somewhat slow (involving at least several seconds). Therefore, S will be discouraged from sending M to multiple recipients with no prior agreements: the cost in terms of both time and computing resources of computing G() 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, 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 faster) as CPU disparities might imply. These ratios are “egalitarian” 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. A stylised illustration of a modern personal computer. ...
palmOne Tungsten T5 Dell Axim X51v Pocket PC Personal digital assistants (usully abbreviated to PDAs) are handheld devices that were originally designed as personal organizers, but became much more versatile over the years. ...
Egalitarianism is the moral doctrine that equality ought to prevail among some group along some dimension. ...
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 ratios 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. In number and more generally in algebra, a ratio is the linear relationship between two quantities of the same unit. ...
Latency is a time delay between the moment something is initiated, and the moment one of its effects begins. ...
See also CPU bound refers to a condition where the time to complete a computation is determined principally by the speed of the central processor and main memory. ...
IO bound refers to a condition in which the time it takes to complete a computation is determined principally by the speed of IO operations. ...
Memory is the ability of the brain to store, retain, and subsequently recall information. ...
In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ...
Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ...
A KMail folder full of spam emails collected over a few days. ...
A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ...
Figure 1. ...
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
- Dwork, C., & Naor, M. (1992). Pricing via Processing or Combating Junk Mail Advances in Cryptology
- Hellman, M. E. (1980). A Cryptanalytic Time-Memory Trade Off. IEEE Transactionson Information Theory
External links |
Feeds |
Contact