18540245
Array allocation taking into account SDRAM characteristics
Multimedia, image processing and other signal processing applications often involve data stored in large arrays. Due to chip area limitation, arrays are typically assigned to off-chip memories, such as DRAM. This being the case, we try to optimize off-chip memory accesses to improve performance. We take the characteristics of the current mainstream SDRAM memory into account. We propose an algorithm to allocate arrays to different banks to increase the probability of utilizing SDRAM's multi-bank characteristic. Experimental results show significant improvement over traditional approaches.
53235373
Performance-optimal clustering with retiming for sequential circuits
195837942
Optimum and heuristic data path scheduling under resource constraints
An integer linear programming model for the scheduling problem in high-level synthesis under resource constraints is presented. The following applications are considered: multicycle operations with nonpipelined or pipelined function units: mutually exclusive operations: functional pipelining: loop-folding; and scheduling under bus constraint. Besides the model, a new technique, called zone scheduling (ZS), is proposed to solve large-size problems. ZS partitions the distribution graph into several zones and sequentially solves the problems contained. A novel feature of this technique is that it schedules more than one control step at a time, allowing a more global view of a scheduling problem to be taken.<<ETX>>
195838317
Data path allocation based on bipartite weighted matching
Proposes a graph-theoretic approach for the data path allocation problem. The problem is decomposed into three subproblems: (1) register allocation, (2) operation assignment, and (3) connection allocation. The first two subproblems are modeled as two bipartite weighted matching problems and solved using the Hungarian method. The third subproblem is solved using a greedy method. It is shown that, by taking the other into consideration while solving one, equally satisfactory results can be obtained, regardless of the order in which (1) and (2) are performed. Two programs, LYRA and ARYL, are implemented which solve the subtasks in different orders. For register allocation, the approach is the first one to guarantee minimal use of registers while being able to take the interconnection cost into account. This research has demonstrated that the bipartite weighted matching algorithm is indeed a good solution for the data path allocation problem.<<ETX>>
6763648
An effective methodology for functional pipelining
We address the problem of given a loop behavior, a target initiation interval and resource constraints, scheduling a loop in a pipelined fashion such that the iteration time (turn-around time) is minimized. The iteration time is an important quality measure of a data path design because of its direct correlationship with both the storage and the control costs. Our scheduler starts with performing an As Soon As Possible Pipelined (ASAPp) scheduling without regard to the resource constraint. It then resolves the resource constraint violations, if there are any, by repeatedly rescheduling some operations.
16396963
Performance-driven interconnection optimization for microarchitecture synthesis
This paper addresses the interconnection synthesis problem in microarchitecture-level designs. With emphasis on the speed of data movement operations, we propose algorithms that take into consideration the effect of each data-transfer-to-bus binding on the data transfer delay time. The delay time is calculated as a function of both data source load and data carrier (bus) load. By balancing loads among hardware components, the data transfer delay time (hence the total execution time) is shortened. We consider two types of problems: resource-constrained binding and performance-constrained binding. Two integer linear programming (ILP) formulations are derived to optimally solve the problems. In order to speed up the computation, a bipartite weighted matching method for the resource-constrained binding and a greedy merging method for the performance-constrained binding are also proposed. Both the ILP formulation generators and the heuristics have been programmed. Experimental results indicate that the proposed algorithms are indeed very effective in optimizing the performance aspect of the interconnection design. >
618071
iMail: a WAP mail retrieving system
This paper proposes iMail, a WAP mail retrieving system designed for wireless handheld devices to access Internet email service. In mobile data networks, the communication bandwidth is limited and the wireless handsets are constrained by small display, powerless CPU, limited memory, and unhandy input/output interface. To support mail retrieving in a mobile environment, we implement several features for iMail: mail filtering, two-phase fetch and pre-defined list reordering. Based on the user's filter options, mail filtering eliminates non-necessary mails sent to a wireless handheld device. Two-phase fetch is used to reduce transmission overhead of message delivery. We use pre-defined list reordering to speed up text typing in the wireless handheld devices. We also propose three mail notification mechanisms for iMail. When a new mail arrives, the mail notification mechanism informs iMail users immediately. Through the descriptions of the iMail features, this paper provides design and implementation guidelines for WAP applications.
38988284
Perfectly Overlapped Generation of Long Runs for Sorting Large Files
A parallel algorithm is presented for quick generation of long sorted runs as the first phase of sorting a large file. It can generate runs of length about 2(m + 2)p on a linear array of p processors each with a heap of size m. Internal computations can be completely overlapped with I/O, and only n + (m + 2)p steps are required to generate the runs from a file of n items. Experiments with the algorithm show that it can give highly satisfactory results in a real environment. A variant of the algorithm is also presented. It is possible that no merge phase is required for sorting a file occupying a whole disk.
2805042
A new random walk model for PCS networks
This paper proposes a new approach to simplify the two-dimensional random walk models capturing the movement of mobile users in personal communications services (PCS) networks. Analytical models are proposed for the new random walks. For a PCS network with hexagonal configuration, our approach reduces the states of the two-dimensional random walk from (3n/sup 2/+3n-5) to n(n+1)/2, where n is the layers of a cluster. For a mesh configuration, our approach reduces the states from (2n2-2n+1) to (n/sup 2/+2n+4)/4 if n is even and to (n/sup 2/+2n+5)/4 if n is odd. Simulation experiments are conducted to validate the analytical models. The results indicate that the errors between the analytical and simulation models are within 1%. Three applications (i.e., microcell/macrocell configuration, distance-based location update, and GPRS mobility management for data routing) are used to show how our new model can be used to investigate the performance of PCS networks.
30979775
Computer telephony integration and its applications
Computer telephony integration (CTI) enhances the capability and flexibility of the switches or the network end equipment by computer technology. This article introduces the components of CTI such as switch-to-host interfaces, application programming interfaces, and resource architectures. Then we describe two CTI configurations: first-party call control and third-party call control. CTI-based telecommunication services such as unified messaging and call center are described. We also illustrate the Integrated Office Telephony System (IOTS), a CTI system developed at Computer Communication Research Laboratories, which integrates the switch and CTI server on a personal computer platform.
28386887
New Systolic Arrays for the Longest Common Subsequence Problem
Abstract New systolic arrays are presented to solve the longest common subsequence (LCS) problem. The first array is based on a previous work to compute the length of an LCS. The second array improves on the first one. The second array is about 1 4 faster than the first array, and each processing element (PE) of the second array requires one less port for both input and output to transfer one less value. Either of the two arrays can be equipped with a content-addressable memory in each PE to recover an LCS. The resulting array requires fewer steps than the previously proposed one.