The problem of minimizing the average time to search for a key in a stored list of keys in a sequential access machine model (SAM) (e.g. a magnetic tape) is considered. The time to access a key in the list and the time to compare it to the given search key are taken into account. The time to access a key in the list is assumed proportional to the distance the head moves from its current location to reach the key. The time to read and compare the key to the search key is taken to be constant. Two classes of algorithms are analyzed and a matching lower bound on the average search time is presented. These results answer an open problem posed by S. Nishihara and H. Nishino (1987) regarding the optimal search algorithm for such a model. It is shown that the organization of the input data is crucial in determining the SAM complexity of the search problem.>

Article Optimal VLSI architectures for multidimensional DFT Share on Authors: G. Bilardi Department of Computer Science, Upson Hall, Cornell University, Ithaca, NY Department of Computer Science, Upson Hall, Cornell University, Ithaca, NYView Profile , S. W. Hornick Andersen Consulting, Center for Strategic Tech. Res., 100 S. Wacker, Chicago, IL Andersen Consulting, Center for Strategic Tech. Res., 100 S. Wacker, Chicago, ILView Profile , M. Sarrafzadeh Dept. of Elec. Eng. and Comp. Sci., The Technological Institute, Northwestern University, Evanston, IL Dept. of Elec. Eng. and Comp. Sci., The Technological Institute, Northwestern University, Evanston, ILView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 265–272https://doi.org/10.1145/72935.72963Online:01 March 1989Publication History 7citation284DownloadsMetricsTotal Citations7Total Downloads284Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we show that distributing the memory of a parallel computer and, thereby, decreasing its granularity allows a reduction in the redundancy required to achieve polylog simulation time for each P-RAM step.Previously, realistic models of parallel computation assigned one memory module to each processor and, as a result, insisted on relatively coarse-grain memory.We propose, on the other hand, a more flexible, but equally valid model of computation, the distributed-memory, bounded-degree network (DMBDN) model.This model allows the use of fine-grain memory while maintaining the realism of a bounded-degree interconnection network.We describe a P-RAM simulation scheme, which is admitted under the DMBDN model, that exploits the increased memory bandwidth provided by a two-dimensional mesh of trees (2DMOT) network to achieve an overhead in memory redundancy lower than that required by other fast, deterministic P-RAM simulations.Specifically, for a deterministic simulation of an n-processor P-RAM on a bounded-degree network, we are able to reduce the number of copies of each variable from O(logn/loglogn) to ®(1) and still simulate each P-RAM step in polylog time.