A variable-precision square root implementation for field programmable gate arrays

Applications requiring variable-precision arithmetic often rely on software implementations because custom hardware is either unavailable or too costly to build. By using the flexibility of the Xilinx XC4010 field programmable gate arrays, we present a hardware implementation of square root that is easily tailored to any desired precision. Our design consists of three types of modules: a control logic module, a data path module to extend the precision in 4-bit increments, and an interface module to span multiple chips. Our data path design avoids the common problem of large fan-out delay in the critical path. Cycle time is independent of precision, and operation latency can be independent of interchip communication delays.Notation S_j square root digit of weight 2^–j - S _j {–1, 0, 1} - S[j] computed square root value as of stepj - S _j ^s sign bit in the representation ofS _j in sign and magnitude form - S _j ^m magnitude bit in the representation ofS _j in sign and magnitude form - w[j] residual at stepj in two's complement carry-save representation - a sum vector in the carry-save representation of 2w[j] - b carry vector in the carry-save representation of 2w[j] - a _i bit of weight 2^–i in the sum vector,a - b_i bit of weight 2^–i in the carry vector,b - T[j]=–S[j – 1]s_j – s _j ² 2^–(j+1) T _i bit of weight 2^–i inT     

Juvenile myoclonic epilepsy

CONCLUSION: We conclude that despite inevitable variability the clinical picture of JME is characteristic. It is easy to diagnose JME if one thinks of it while the history should be thoroughly analyzed. An EEG recording during sleep confirms the diagnosis. An early diagnosis of JME permits adequate prognosis of the subsequent course of epilepsy, and adequate therapy brings remission in most of the patients. If treatment starts following the large number of severe GTC seizures, the response to therapy is incomplete. The persistency of the illness throughout the life, the need for continuous medication and therapeutic unresponsiveness in cases with late diagnosis, do not justify the increasing misconception that JME is of benign nature. Diagnosis of JME is rare because of insufficient familiarily of physicians with the illness. BACKGROUND: Juvenile myoclonic epilepsy (JME) is an idiopathic generalized epileptic syndrome characterized with the combination of myoclonic, generalized tonic-clonic (GTC) and absence seizures that are readily provoked by sleep deprivation. PATIENTS: Forty-three patients, aged from 14 to 51 years, participated in a 5-year follow-up study. Diagnosis was made according to the criteria (Table 1) for diagnosis of JME set by Panayiotopoulos et al. (1994). Nineteen patients made their first contact with a neurologist at the Institute of Neurology and were diagnosed as JME, while the remaining 24 were referred to from other medical institutions with a diagnosis of therapy resistant to focal epilepsy. All patients underwent a somatic and neurological examination, "mini mental test," EEG in waking and CT scan of the brain. Some patients had EEG performed during sleep and some had MRI of the head. RESULTS: JME began between 9 and 26 (average 17) years. All patients had myoclonic seizures, 98% had GTC and 23% absence seizures. The first myoclonic seizure occurred between 9 and 24 years while the frst GTC seizure occurred between 10 and 32 years. Myoclonic seizures (83% of patients) and GTC seizures (70% of patients) occurred most often immediately after awaking. The most frequent provocative factors were insufficient sleep, alcohol abuse and tiredness. Epilepsy in the family was present in 39%, focal neurological deficiency in 9% and pathological findings on of CT and MRI in 7% of patients. Waking EEG was pathological in 77% of patients; it included generalized spike-wave discharges in 73%, multiple spike-wave complexes in 33% and focal discharges in 12% of patients, respectively. In all 26 patients tested, sleep EEG was pathological most often with multiple spike-wave complexes in 85% and 3-4 Hz spike-wave complexes in 57% of patients. The correct diagnosis of JME following a comprehensive examination was made in 24 (56%) patients after a delay of 1 to 35 years. In 24 patients with delayed diagnosis of JME the replacement of earlier medication with valproic acid (VPA) induced remission in 18 patients (75%) while 1 patient (4%) experienced a reduction in the number of seizures. Five patients (21%) did not respond to VPA medication: 2 due to a weak compliance, another 2 due to inefficient medication and 1 because of the preexistent malabsorption syndrome. In 19 patients (44%) with initial diagnosis of JME, VPA was introduced immediately upon diagnosis. Of them, 15 (79%) had excellent response to VPA, 1 refused therapy and for 3 patients there is no information. In 2 patients VPA was substituted due to side effects (hepatotoxicity and alopetia) with lamotrigine (low doses), which brought about decrease in frequency and mitigation in myoclonic seizures.     

Fast radix-2 division with quotient-digit prediction

An implementation of a radix-2 division unit is presented that uses prediction of the quotient digit. This prediction allows the concurrent computation of the quotient digit and the partial remainder. To achieve a simple quotient-digit selection, resulting in a step time roughly half of that of SRT division (without prediction), a simple estimate of the partial remainder is used, which requires that the divisor be scaled close to unity. This prescaling is simple to implement and increases the execution time by two cycles. We estimate a speed-up of 1.5 with respect to SRT division with redundant remainders.     

Comments on "A carry-free 54 b/spl times/54 b multiplier using equivalent bit conversion algorithm"

For original paper see ibid., vol. 36, no. 10, p. 1538-1545 (Oct. 2001). In the aforementioned paper by Kim et al., a multiplier is presented which produces the result in radix-2 signed-digit representation. It is claimed that this representation can be converted into conventional magnitude representation by an algorithm which has no carry propagation. To the commenters this algorithm seems incorrect. The critical situation is a string which consists of a sequence of zeros followed by a -1; in such a case a carry is needed and the algorithm proposed is deemed incorrect. Consequently, it is pointed out that the proposed algorithm produces a correct multiplication result in conventional magnitude representation only if the signed-digit string does not have a sequence of 0's followed by a -1. The commenters show a multiplication example using the proposed conversion algorithm in which this situation occurs.     

Architectural support for goal management in flat concurrent Prolog

A special-purpose architectural support that reduces the goal-management execution time in flat concurrent Prolog (FCP) is described. The architectural support consists of a dedicated goal-management unit that executes high-level goal-management operations concurrently with goal-reduction operations. The efficient execution of goal-management instructions is realized using a goal cache that stores recently spawned goals. It is shown that operations such as goal-switching, spawning, and halting are efficiently performed by changing their status in the goal cache. More complex operations, such as goal suspension and activation are decoupled from goal reduction by using two suspension tables and activation queues. Using an analytic performance model, it is shown that, for the systems development workload, which consists of large FCP programs, the overhead of software-implemented goal management is 50% of the program execution time. This is reduced up to 3% using the goal-management unit and the goal cache, resulting in a speedup of almost 2. The results are generalized for other workloads that exhibit different goal-management complexities     

Gate array implementation of on-line algorithms for floating-point operations

We present gate array designs of on-line arithmetic units for radix-2 floating-point addition, multiplication and division operations. Performance and complexity characteristics of the implementations of on-line arithmetic units are discussed and compared with those of the compatible conventional floating-point algorithms implemented in the same technology.     

Performance evaluation of a simulated data-flow computer with low-resolution actors

In the ambition to go beyond a single-processor architecture, to enhance programmability, and to take advantage of the power brought by VLSI devices, data-flow systems and languages were devised. Indeed, due to their functional semantics, these languages offer promise in the area of multiprocessor systems design and will possibly enable the development of computers comprising large numbers of processors with a corresponding increase in performance. Several important design problems have to be surmounted and are described here. We thus present a “variable-resolution” scheme, where the level of primitives can be selected so that the overhead due to the data-flow mode of operation is reduced. A deterministic simulation of a data-flow machine with a variable number of processing elements was undertaken and is described here. The tests were performed using various program structures such as directed acyclic graphs, vector operations, and array handling. The performance results observed confirm the advantage of actors with variable size and indicate the presence of a trade-off between overhead control and the need to control parallelism in the program. We also look at some of the communication issues and examine the effect of several interconnection networks (dual counter-rotating rings, daisy chain, and optimal double loop network) on the performance. It is shown how increasing communication costs induce a performance degradation that can be masked when the size of the basic data-flow actor is increased. The asociative memory cycle time is also changed with similar conclusions. Finally, the lower-resolution scheme is applied to the array handling case; the observations confirm the advantage of a more complex actor at the array level.     

A FPGA-based Library for On-Line Signal Processing

A library of on-line arithmetic structures is presented. Their ability to produce and consume the most significant digit first allows subsequent computations to begin earlier, shortens the execution time of variable precision and composite operations, and simplifies interconnection networks which can help preserve high clock rates in large digit-serial designs. More importantly, designers can interconnect individual units without designing intermediate structures to reformat data, a luxury that is currently unavailable to FPGA designers wishing to use bit-serial arithmetic. The on-line structures introduced are small, and can be easily combined to yield more powerful blocks. The library's applicability to signal processing applications is demonstrated with the DFT, DCT, and FIR filter. Results indicate high area efficiency and rapid execution speed.     

TEMPERATURE AND BURIAL HISTORY MODELLING OF THE DRMNO AND MARKOVAC DEPRESSIONS, SE PANNONIAN BASIN, SERBIA

We have modelled the subsidence, thermal and maturation history of the Drmno and Markovac depressions in the SE Pannonian Basin (Serbia) in order to calculate quantities of generated, expelled and migrated hydrocarbons. Stratigraphic, lithofacies, structural, thermal and geochemical data were used to create a conceptual model of the basin's evolution to depths of 5,000m. The models were calibrated using present-day temperature and vitrinite reflectance data from representative wells. The results show that in the centres of these depressions, possible Badenian and pre-Badenian (i.e. Middle and Lower Miocene) source rocks are sufficiently mature to have generated oil and gas.
Maturity data reveal significant differences in heat flow during times when maximum palaeotemperatures were reached. From these data high heat flows can only be deduced for some of the wells, whereas similar high heat flows are deduced from present-day temperature data. Future research is necessary to resolve in detail the geologic evolution of the study area which resulted in the significant differences between the Mio/Pliocene and Recent heat flows.
Petroleum generation is taking place at depths below 2,000m in both depressions, mainly from Pre-Badenian source rocks which contain Type II-III kerogen and which appear to have a high petroleum generation potential.     

Conventional and on-line arithmetic designs for high-speed recursive digital filters

Designs using conventional and on-line arithmetic for performing the recursive computations of Second-Order Direct-Form IIR filters are implemented in a 0.7μ HCMOS gate array technology. The new conventional (bit-parallel) design using two levels of scattered lookahead achieves a rate of 104 Msamples/second. The design eliminates carry propagate addition from the recursive loop and uses radix-4 recoding to reduce the number of partial products. The on-line design is an improved radix-4 multiply-add (MA) module. Two arrays based on the on-line MA module are developed to achieve rates of 128 Msamples/second with two levels of scattered lookahead. Performance and cost comparisons of the designs provide insights into the most appropriate designs to be used for a given word length.