In this paper we introduce a new Simulated Annealing-based timing-driven placement algorithm for fpgas. This paper has three main contributions. First, our algorithm employs a novel method of determining source-sink c...
详细信息
ISBN:
(纸本)9781581131932
In this paper we introduce a new Simulated Annealing-based timing-driven placement algorithm for fpgas. This paper has three main contributions. First, our algorithm employs a novel method of determining source-sink connection delays during placement. Second, we introduce a new cost function that trades off between wire-use and critical path delay, resulting in significant reductions in critical path delay without significant increases in wire-use. Finally, we combine connection-based and path-based timing-analysis to obtain an algorithm that has the low time-complexity of connection-based timing-driven placement, while obtaining the quality of path-based timing-driven placement. A comparison of our new algorithm to a well known non-timing-driven placement algorithm demonstrates that our algorithm is able to increase the post-place-and-route speed (using a full path-based timing-driven router and a realistic routing architecture) of 20 MCNC benchmark circuits by an average of 42%, while only increasing the minimum wiring requirements by an average of 5%.
In recent years the application space of reconfigurable devices has grown to include many platforms with a strong need for fault tolerance. While these systems frequently contain hardware redundancy to allow for conti...
详细信息
ISBN:
(纸本)9781581131932
In recent years the application space of reconfigurable devices has grown to include many platforms with a strong need for fault tolerance. While these systems frequently contain hardware redundancy to allow for continued operation in the presence of operational faults, the need to recover faulty hardware and return it to full functionality quickly and efficiently is great. In addition to providing functional density, fpgas provide a level of fault tolerance generally not found in mask-programmable devices by including the capability to reconfigure around operational faults in the field. In this paper, incremental CAD techniques are described that allow functional recovery of fpga design configurations in the presence of single or multiple operational faults. Our preferred approach to fault recovery takes advantage of device routing hierarchy in architectural families such as Xilinx Virtex and Altera Apex to quickly swap unused logic and routing resources in place of faulty ones within logic clusters. These algorithms allow for straightforward implementation within a local fault-tolerant system without the need to access a remote processing location. If initial recovery attempts through localized swapping fail, an incremental router based on the widely-used PathFinder maze routing algorithm can be applied remotely in an attempt to form connections between newly-allocated logic and interconnect based on the history of the initial design route.
A method for evaluating and constructing sparse crossbars which are both area efficient and highly routable is presented. The evaluation method uses a network flow algorithm to accurately compute the percentage of ran...
详细信息
ISBN:
(纸本)9781581131932
A method for evaluating and constructing sparse crossbars which are both area efficient and highly routable is presented. The evaluation method uses a network flow algorithm to accurately compute the percentage of random test vectors that can be routed. The construction method attempts to maximize the spread of the switch locations, such that any given subset of input wires can connect to as many output wires as possible. Based on Hall's Theorem, we argue that this increases the likelihood of routing. The hardest test vectors to route are those which attempt to use all of the crossbar outputs. Results in this paper show that area-efficient sparse crossbars can be constructed by providing more outputs than required and a sufficient number of switches. In a few specific case studies, it is shown that sparse crossbars with about 90% fewer switches than a full crossbar can be constructed, and these crossbars are capable of routing over 95% of randomly chosen routing vectors. In one case, a new switch matrix which can replace the one in the Altera FLEX8000 family is shown. This new switch matrix uses approximately 14% more transistors, yet can increase the routability of the most difficult test vectors from 1% to over 96%.
Most advanced forms of security for electronic transactions rely on the public-key cryptosystems developed by Rivest, Shamir and Adleman. Unfortunately, these systems are only secure while it remains difficult to fact...
详细信息
ISBN:
(纸本)9781581131932
Most advanced forms of security for electronic transactions rely on the public-key cryptosystems developed by Rivest, Shamir and Adleman. Unfortunately, these systems are only secure while it remains difficult to factor large integers. The fastest published algorithms for factoring large numbers have a common sieving step. These sieves collect numbers that are completely factored by a set of prime numbers that are known in advance. Furthermore, the time required to execute these sieves currently dominates the runtime of the factoring algorithms. We show how the sieving process can be mapped to the Mojave configurable computing architecture. The mapping exploits unique properties of the sieving algorithms to fully utilize the bandwidth of a multiple bank interleaved memory system. The sieve has been mapped to a single programmable hardware unit on the Mojave computer, and achieves a clock frequency of 16 MHz. The full system implementation sieves over 28 times faster than an UltraSPARC Workstation. A simple upgrade to 8 ns SRAMs will result in a speedup factor of 160.
The paper describes the implementation of a systolic array for a multilayer perceptron on a Virtex XCV400 fpga with a hardware-friendly learning algorithm. A pipelined adaptation of the on-line backpropagation algorit...
详细信息
ISBN:
(纸本)0769507662
The paper describes the implementation of a systolic array for a multilayer perceptron on a Virtex XCV400 fpga with a hardware-friendly learning algorithm. A pipelined adaptation of the on-line backpropagation algorithm is shown. Parallelism is better exploited because both forward and backward phases can be performed simultaneously. We can implement very large interconnection layers by using large Xilinx devices with embedded memories alongside the projection used in the systolic architecture. These physical and architectural features - together with the combination of fpga reconfiguration properties with a design flow based on generic VHDL - create an easy, flexible, and fast method of designing a complete ANN on a single fpga. The result offers a high degree of parallelism and fast performance.
In this paper we present a novel coverification concept for embedded microcontrollers that satisfies industrial requirements. Based on a commercially available CPU in-circuit emulator coupled with fpga boards, it veri...
详细信息
ISBN:
(纸本)0769507662
In this paper we present a novel coverification concept for embedded microcontrollers that satisfies industrial requirements. Based on a commercially available CPU in-circuit emulator coupled with fpga boards, it verifies the correctness of an implementation in terms of function and timing within a real-world environment. Using our system, the software engineer can write, test and optimize programs for a chip that is not yet physically existent. In addition the system is used to obtain software module characterization data required for system partitioning. Its ability to integrate analog circuitry enables verification of the complete system-on-chip. Our methodology is fully integrated into the ASIC design flow providing ease of use and a high level of verification accuracy.
The proceedings contains 25 papers from the 1998 acm/sigdainternationalsymposium on fieldprogrammablegatearrays (fpga). Topics discussed include: new fpga architectures;technology mapping for fpgas;multi-fpga sys...
详细信息
The proceedings contains 25 papers from the 1998 acm/sigdainternationalsymposium on fieldprogrammablegatearrays (fpga). Topics discussed include: new fpga architectures;technology mapping for fpgas;multi-fpga systems & other reprogrammable architectures;partitioning and floor planning for fpgas;fault detection and fault tolerance for fpgas;fast computer aided design (CAD) tools for fpgas;time multiplexed fpgas;fpgas with embedded memory;and programmable architectures with special features.
Dynamically reconfigurable fpgas have the potential to dramatically improve logic density by time-sharing a physical fpga device. This paper presents a network-flow based partitioning algorithm for dynamically reconfi...
详细信息
Dynamically reconfigurable fpgas have the potential to dramatically improve logic density by time-sharing a physical fpga device. This paper presents a network-flow based partitioning algorithm for dynamically reconfigurable fpgas based on the architecture in [2]. Experiments show that our approach outperforms the enhanced force-directed scheduling method in [2] in terms of communication cost.
An approach for runtime mapping is proposed that utilizes self-reconfigurability of multicontext fieldprogrammablegatearrays (fpga) to achieve very high speedups over existing approaches. The idea is to design and ...
详细信息
An approach for runtime mapping is proposed that utilizes self-reconfigurability of multicontext fieldprogrammablegatearrays (fpga) to achieve very high speedups over existing approaches. The idea is to design and map logic onto a multicontext fpga that in turn maps problem instance dependent logic onto other contexts of the same fpga. As a result, computer aided design tools need to be used just once for each problem and not once for every problem instance as is usually done.
A new search-based satisfiability (SAT) formulation that can handle entire fieldprogrammablegate array (fpga), routing all nets concurrently is presented. The approach relies on a recently developed SAT engine that ...
详细信息
A new search-based satisfiability (SAT) formulation that can handle entire fieldprogrammablegate array (fpga), routing all nets concurrently is presented. The approach relies on a recently developed SAT engine that uses systematic search with conflict directed nonchronological backtracking, capable of handling very large SAT instances. Preliminary experimental results suggest that this approach to fpga routing is more viable than earlier binary decision diagram-based method.
暂无评论