The performance of multilective VLSI algorithms
type: Item
instance of: scholarly article
title: The performance of multilective VLSI algorithms
zbMATH Open document ID: 0583.68021
DOI: 10.1016/0022-0000(84)90033-3
author: John Savage
published in: Journal of Computer and System Sciences
publication date: 1984-01-01T00:00:00Z
review text: Several models for VLSI algorithms have been postulated. The one treated in this paper differs from most others in that it explicitly permits inputs to be read multiple times, that is, algorithms used are multilective. The way in which lower bounds derived for VLSI depend on the number of times and places at which inputs are read are explored. The contribution of this paper is to present methods for treating such multilective algorithms and to apply these methods to a large variety of functions and predicates. Figuring prominently in this work is the planar circuit size of a problem. It is used to derive lower bounds to various area-time products. Also presented here is a method for deriving lower bounds on the area required by multilective algorithms.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3934406
zbMATH Keywords: multilective algorithms
zbMATH Keywords: planar circuit size
zbMATH Keywords: lower bounds
zbMATH Keywords: area-time products
MaRDI profile type: Publication
full work available at URL: 0022-0000(84)90033-3
OpenAlex ID: W2083381826
cites work: The Area-Time Complexity of Binary Multiplication
cites work: Information transfer and area-time tradeoffs for VLSI multiplication
cites work: Area-time tradeoffs for matrix multiplication and related problems in VLSI models
cites work: Q4109584
cites work: A Separator Theorem for Planar Graphs
cites work: Q4138141
cites work: Computational Work and Time on Finite Machines
cites work: Time-space tradeoffs for computing functions, using connectivity properties of their circuits
cites work: Q4190139
cites work: Space-Time Trade-Offs for Banded Matrix Problems
cites work: Q4773298
cites work: Area-time optimal VLSI networks for multiplying matrices
cites work: Space-time trade-offs on the FFT algorithm
description: scientific article; zbMATH DE number 3934406