Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Debasish Das

dblp:94/6029 · DBLP profile ↗
← Back
23ranked-venue papers
16as first author
1since 2021 · last 2021
0000-0002-2020-1497ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Systems, architecture and hardware · 14 · 8 first-authorApplied, interdisciplinary, general and emerging computing · 5 · 5 first-authorArtificial intelligence and machine learning · 4 · 3 first-author · 1 since 2021Databases, data management, data science and information retrieval · 1 · 1 first-authorGraphics, computer vision, multimedia, augmented reality and games · 1

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Computer architecture, parallel and distributed computing, and storage systems
7 papers
Electronic design automation · 79% Parallel and multicore computing · 6% Energy-efficient computing · 5%
Interdisciplinary, comprehensive, and emerging computing
1 paper
Environmental and earth informatics · 100%
Theoretical computer science
1 paper
Mathematical optimization · 100%

Topics — the 19 heaviest of 19, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Electronic design automation › timing analysis
static timing analysis
0.222011
A Novel Moment Based Framework for Accurate and Efficient Static Timing Analysis · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2011
Pessimism Reduction in Coupling-Aware Static Timing Analysis Using Timing and Logic Filtering · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2010
Electronic design automation › timing analysis › static timing analysis
crosstalk-aware timing analysis
0.112010
Pessimism Reduction in Coupling-Aware Static Timing Analysis Using Timing and Logic Filtering · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2010
Electronic design automation
timing analysis
0.112010
Pessimism Reduction in Coupling-Aware Static Timing Analysis Using Timing and Logic Filtering · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2010
Environmental and earth informatics
remote sensing
0.112009
Active Selection of Sensor Sites in Remote Sensing Applications · ICDM 2009
Electronic design automation
circuit sizing
0.112009
Gate Sizing by Lagrangian Relaxation Revisited · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2009
Electronic design automation › physical design › clock network synthesis
clock skew optimization
0.112009
Gate Sizing by Lagrangian Relaxation Revisited · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2009
Electronic design automation › physical design
gate sizing
0.112009
Gate Sizing by Lagrangian Relaxation Revisited · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2009
Electronic design automation › physical design
timing optimization
0.112009
Gate Sizing by Lagrangian Relaxation Revisited · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2009
Mathematical optimization
lagrangian relaxation
0.112009
Gate Sizing by Lagrangian Relaxation Revisited · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2009
Energy-efficient computing
leakage power reduction
0.112005
Hierarchical LUT structures for leakage power reduction (abstract only) · FPGA 2005
Parallel and multicore computing
parallel algorithms
0.021999
A New Network Topology with Multiple Meshes · IEEE Trans. Computers 1999
An Efficient Sorting Algorithm on the Multi-Mesh Network · IEEE Trans. Computers 1997
Electronic design automation › timing analysis
pessimism reduction
0.012010
Pessimism Reduction in Coupling-Aware Static Timing Analysis Using Timing and Logic Filtering · IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2010
Interconnection networks and networks-on-chip
network topology
0.021999
A New Network Topology with Multiple Meshes · IEEE Trans. Computers 1999
An Efficient Sorting Algorithm on the Multi-Mesh Network · IEEE Trans. Computers 1997
Interconnection networks and networks-on-chip
routing and broadcasting
0.011999
A New Network Topology with Multiple Meshes · IEEE Trans. Computers 1999
Parallel and multicore computing › parallel algorithms › sorting
parallel sorting
0.011997
An Efficient Sorting Algorithm on the Multi-Mesh Network · IEEE Trans. Computers 1997
Reconfigurable computing and FPGAs › FPGA architecture
configurable logic block
0.012005
Hierarchical LUT structures for leakage power reduction (abstract only) · FPGA 2005
Processor architecture and microarchitecture › arithmetic unit
arithmetic unit design
0.011995
Implementation of Four Common Functions on an LNS Co-Processor · IEEE Trans. Computers 1995
Integrated circuit design
digital circuit design
0.011995
Implementation of Four Common Functions on an LNS Co-Processor · IEEE Trans. Computers 1995
Processor architecture and microarchitecture › computer arithmetic
elementary function evaluation
0.011995
Implementation of Four Common Functions on an LNS Co-Processor · IEEE Trans. Computers 1995

Methods — techniques the papers use, named apart from their topics

min-cost network flow · 0.2method of feasible directions · 0.2lagrangian relaxation · 0.2elmore delay model · 0.2moment-based analysis · 0.1convolution · 0.1timing filtering · 0.1logic filtering · 0.1iterative analysis · 0.1uncertainty sampling · 0.1spatial diversity · 0.1vdd gating · 0.1
YearPublicationVenuePosition
2021 Meta-Heuristic Algorithms-Tuned Elman vs. Jordan Recurrent Neural Networks for Modeling of Electron Beam Welding Process
Debasish Das, Amit Kumar Das 0003, Abhishek Rudra Pal, Sanjib Jaypuria, Dilip Kumar Pratihar, Gour Gopal Roy
Neural Process. Lett.1
2019 Automated Security Testing Framework for Validating Content Rights On Video Streaming Devices
abstract
Proliferation of high speed internet services and mass adoption of smart phones and internet enabled smart devices has led to a meteoritic rise in streaming video services around the globe. As streaming audio-video content takes center-stage in this digital era, “Cut-the-Cord” phenomenon has gained significant momentum all over the globe. New streaming models like Over-the-Top (OTT) services have disrupted this industry globally. OTT platforms like Netflix, Amazon Prime, YouTube, Sony Crackle, BBC iPlayer have gained lot of market share in the recent years. In India alone, there are more than 40 video streaming services [1] like Hotstar, AirtelTV, Voot, Sony Liv, JioTV and the list is growing by the day. However, streaming video applications, face constant challenges with respect to security of content rights across the streaming value chain. A leading global research firm KPMG, in a recent report suggests that, global streaming players could suffer losses of over 50 billion dollars (USD) due to pirated content in the next few years. Similarly a recent report released by FICCI highlights the fact that, upto 30% of overall film sector revenue in India has been lost due to piracy alone. As millions of internet videos get streamed on various consumer devices, risks of security breaches, online piracy and video hacking, pose considerable challenge for the entire video streaming industry. Therefore, it becomes absolutely essential for the video content creators, aggregators and distributors to adopt best-in-class secure development methodologies along with cutting edge security testing techniques to protect digital video assets. This requires special focus beyond traditional quality assurance (QA) and conventional security testing techniques like Pen Testing, Vulnerability Assessment etc. In this paper we propose a unique automated security testing framework focusing on critical aspects of the video streaming domain. In-order to provide a holistic model for enhancing cyber security aspects of streaming video systems, we expanded our earlier research work [3], [4] to cover latest content security concepts like Digital Rights Management (DRM), High-bandwidth Digital Content Protection (HDCP). Our proposed security testing methodology uses latest automation techniques and proven statistical methods to yield more than 90% better efficiencies with accuracy as high as 97%.
Debasish Das
TENCON1
2018 Phenomenological model-based study on electron beam welding process, and input-output modeling using neural networks trained by back-propagation algorithm, genetic algorithms, particle swarm optimization algorithm and bat algorithm
Debasish Das, Dilip Kumar Pratihar, Gour Gopal Roy, Abhishek Rudra Pal
Appl. Intell.1
2015 Detection of Cross-Site Scripting Attack under Multiple Scenarios
abstract
Web-application attacks are considered to be one of the major security concerns of a large number of applications, especially those deployed in health care, banking and e-business operations. These applications must involve high security in addition to other application requirements such as friendliness, effectiveness and efficiency in service provided to the end users. In this paper, we focus on security vulnerabilities resulting from generic input validation problems that may cause cross-site scripting (XSS) attacks. We take a look at the types of XSS attacks and current practices for their detection and identify the research issues and challenges. We propose a method for the detection of XSS attacks. The detection method identifies a malicious execution sequence based on the initialized list of—legitimate execution sequences and malicious strings or malicious literals generated during a training phase. The initialized lists are stored into four different Web-Application Execution Profiles (WAEPs) corresponding to four different attack scenarios. The detection module searches the run-time sequence in the respective WAEPs. We test our method for the detection of three different categories of XSS attacks under four different attack scenarios—two in the client side and two in the web-application server. Satisfactory results have been found under all the four scenarios.
Debasish Das, Utpal Sharma, Dhruba Kumar Bhattacharyya
Comput. J.1
2015 A Bayesian Sparse Generalized Linear Model With an Application to Multiscale Covariate Discovery for Observed Rainfall Extremes Over the United States
abstract
Predictive insights on extreme and rare events are important across multiple disciplines ranging from hydrology, climate, and remote sensing to finance and security. Characterizing the dependence of extremes on covariates can help in identification of plausible causal drivers and may even inform predictive modeling. However, despite progress in the incorporation of covariates in the statistical theory of extremes and in sparse covariate discovery algorithms, progress has been limited for high-dimensional data where the number of covariates is large. In this paper, we propose a general-purpose sparse Bayesian framework for covariate discovery based on a Poisson description of extremes frequency and a hierarchical Bayesian description of a sparse regression model. We obtain posteriors over regression coefficients, which indicate dependence of extremes on the corresponding covariates, using a variational Bayes approximation. Experiments with synthetic data demonstrate the ability of the approach to accurately characterize dependence structures. The method is applied to discover the covariates affecting the frequency of precipitation extremes obtained from station-level observations over nine climatologically homogeneous regions within the continental U.S. The candidate covariates at multiple spatial scales represent station-level as well as regional and seasonal atmospheric condition, indices that attempt to capture large-scale ocean-based climate oscillators and hence natural climate variability, as well as global warming. Our results confirm the dependence structures that may be expected from known precipitation physics and generate novel insights, which can inform physical understanding and perhaps even predictive modeling.
Debasish Das, Auroop R. Ganguly, Zoran Obradovic
IEEE Trans. Geosci. Remote. Sens.1
2012 Spatially penalized regression for dependence analysis of rare events: A study in precipitation extremes
abstract
Discovery of dependence structure between precipitation extremes and other climate variables (covariates) within a smaller spatial and temporal neighborhood is an important step in better understanding the drivers of this complex phenomenon as well as short-term prediction of extremes occurrence. Apart from the inherent spatio-temporal variability of the dependence, it is further complicated by the availability of the covariates at different vertical levels. The above problem can be split into three different sub-problems. Firstly, a spatio-temporal neighborhood of influence has to be discovered, which can be different for different locations. Secondly, the dependence structure between the precipitation extremes and the covariates has to be discovered within this neighborhood and thirdly, it has to be investigated whether this dependence structure can be exploited for any predictive power. Climate scientists have already discovered some physics-based relations between some of the covariates (e.g. temperature, relative humidity, precipitable water etc.) and precipitation extremes. We are exploring data-dependent alternatives for these problems and any possibility of incorporating the physics-based relations into the resulting data model. In particular, we used elastic net-based sparse optimization technique which solves all three problems of neighborhood discovery, covariate dependence discovery and predictive modeling and at the same time maintains the interpretability of the resulting model. Preliminary results look promising and show potential for some interesting knowledge discovery. We are currently exploring non-linear correlations and the alternatives to combine the physics-based relationships into the data model.
Debasish Das, Auroop R. Ganguly, Snigdhansu Chatterjee, Vipin Kumar 0001, Zoran Obradovic
IGARSS1
2011 A Novel Moment Based Framework for Accurate and Efficient Static Timing Analysis
abstract
A novel methodology for accurate and efficient static timing analysis is presented in this paper. Our methodology uses the traditional cell library table structure with one modification. The cell library tables are filled with the gate output signal moments instead of the gate output 50% delay and output slew. Using only few moments gives much better accuracy and visibility for the gate output waveform than using the time domain information. Simple convolution of the gate output moments with the interconnect moments yields the signal moments at the stage output. The parameters of the gate input signal, which are used for the table access of the successive stage, are directly computed from the predecessor stage output moments using the closed form expressions without having to explicitly transform the frequency domain moments to time domain. Thus, the interconnects and the gates are treated in a unified moment-based homogeneous framework. The proposed approach inherits the classical cell library tables approach efficiency with even reduced computation complexities. As compared to the classical cell library table approach, the proposed approach accounts for the increasingly nonlinear and non-monotonic waveform shapes which are prohibitively difficult to represent in the classical approaches. In contrary to the classical approaches, increasing the accuracy in the novel approach is made flexible and can be achieved by simply using more moments. To illustrate the concept and prove its merits, multiple examples are presented with 2-3 moments which maintain accuracy within 1%-3% as compared to SPICE.
Ahmed Shebaita, Debasish Das, Dusan Petranovic, Yehea I. Ismail
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.2
2011 FA-STAC: An Algorithmic Framework for Fast and Accurate Coupling Aware Static Timing Analysis
abstract
This paper presents an algorithmic framework for fast and accurate static timing analysis considering coupling. With technology scaling to smaller dimensions, the impact of coupling induced delay variations can no longer be ignored. Timing analysis considering coupling is iterative, and can have considerably larger run-times than a single pass approach. We propose two different classes of coupling delay models: heuristic-based coupling model and current source-based coupling model, and present techniques to increase the convergence rate of timing analysis when such coupling models are employed. Our proposed coupling model show promising accuracy improvements compared to SPICE. Experimental results on ISCAS85 benchmarks validates the effec tiveness of our efficient iteration scheme. Our iteration algorithm obtained speedups of up to 62.1 % using a heuristic coupling model while 2.7 x using a current-based coupling model in comparison to traditional approaches.
Debasish Das, Ahmed Shebaita, Hai Zhou 0001, Yehea I. Ismail, Kip Killpack
IEEE Trans. Very Large Scale Integr. Syst.1
2010 iRetILP: an efficient incremental algorithm for min-period retiming under general delay model
abstract
Retiming is one of the most powerful sequential transformations that relocates flip-flops in a circuit without changing its functionality. The min-period retiming problem seeks a solution with the minimal clock period. Since most min-period retiming algorithms assume a simple constant delay model that does not take into account many prominent electrical effects in ultra deep sub micron vlsi designs, a general delay model was proposed to improve the accuracy of the retiming optimization. Due to the complexity of the general delay model, the formulation of min-period retiming under such model is based on integer linear programming (ILP). However, because the previous ILP formulation was derived on a dense path graph, it incurred huge storage and running time overhead for the ILP solvers and the application was limited to small circuits. In this paper, we present the iRetILP algorithm to solve the min-period retiming problem efficiently under the general delay model by formulating and solving the ILP problems incrementally. Experimental results show that iRetILP is on average 100× faster than the previous algorithm for small circuits and is highly scalable to large circuits in term of memory consumption and running time.
Debasish Das, Jia Wang 0003, Hai Zhou 0001
ASP-DAC1
2010 Regression Learning with Multiple Noisy Oracles
abstract
In regression learning, it is often difficult to obtain the true values of the label variables, while multiple sources of noisy estimates of lower quality are readily available. To address this problem, we propose a new Bayesian approach that learns a regression model from data with noisy labels provided by multiple oracles. The proposed method provides closed form solution for model parameters and is applicable to both linear and nonlinear regression problems. In our experiments on synthetic and benchmark datasets this new regression model was consistently more accurate than a model trained with averaged estimates from multiple oracles as labels.
Kosta Ristovski, Debasish Das, Vladimir Ouzienko, Yuhong Guo, Zoran Obradovic
ECAI2
2010 Pessimism Reduction in Coupling-Aware Static Timing Analysis Using Timing and Logic Filtering
abstract
With continued scaling of technology into nanometer regimes, the impact of coupling induced delay variations is significant. While several coupling-aware static timers have been proposed, the results are often pessimistic with many false failures. We present an integrated iterative timing filtering and logic filtering based approach to reduce pessimism. We use a realistic coupling model based on arrival times and slews, and show that non-iterative pessimism reduction algorithms proposed in previous research may give potentially non-conservative timing results. On a functional block from an industrial 65 nm microprocessor, our algorithm produced a maximum pessimism reduction of 11.18% of cycle time over converged timing filtering analysis that does not consider logic constraints.
Debasish Das, Kip Killpack, Chandramouli V. Kashyap, Abhijit Jas, Hai Zhou 0001
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.1
2009 Active Selection of Sensor Sites in Remote Sensing Applications
abstract
In a data-mining approach, a model for estimation of aerosol optical depth (AOD) from satellite observations is learned using collocated satellite and ground-based observations. For accurate learning of such a spatio-temporal model, it is important to collect ground-based data from a large number of sites. The objective of this project is to determine appropriate locations for the next set of ground-based data collection sites to maximize accuracy of AOD estimation. Ideally, a new site should capture the most significant unseen aerosol patterns and should be the least correlated with the previously observed patterns. We propose achieving this aim by selecting the locations on which the existing prediction model is the most uncertain. Several criteria were considered for site selection, including uncertainty, spatial diversity, similarity in temporal pattern, and their combination. Extensive experiments on globally distributed data over 90 AERONET sites from the years 2005 and 2006 provide strong evidence that sites selected using the proposed algorithms improve the overall AOD prediction accuracy at a faster rate than those selected randomly or based on spatial diversity among sites.
Debasish Das, Zoran Obradovic, Slobodan Vucetic
ICDM1
2009 Gate Sizing by Lagrangian Relaxation Revisited
abstract
In this paper, we formulate the generalized convex sizing (GCS) problem that unifies the sizing problems and applies to sequential circuits with clock-skew optimization. We revisit the approach to solve the sizing problem by Lagrangian relaxation, point out several misunderstandings in the previous paper, and extend the approach to handle general convex delay functions in the GCS problems. We identify a class of proper GCS problems whose objective functions in the simplified dual problem are differentiable and transform the simultaneous sizing and clock-skew optimization problem into a proper GCS problem. We design an algorithm based on the method of feasible directions and min-cost network flow to solve proper GCS problems. The algorithm will provide evidences for infeasible GCS problems according to a condition derived by us. Experimental results confirm the efficiency and the effectiveness of our algorithm when the Elmore delay model is used.
Jia Wang 0003, Debasish Das, Hai Zhou 0001
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.2
2008 Pessimism reduction in coupling-aware static timing analysis using timing and logic filtering
abstract
With continued scaling of technology into nanometer regimes, the impact of coupling induced delay variations is significant. While several coupling-aware static timers have been proposed, the results are often pessimistic with many false failures. We present an integrated iterative timing filtering and logic filtering based approach to reduce pessimism. We use a realistic coupling model based on arrival times and slews and show that non-iterative pessimism reduction algorithms proposed in previous research may give potentially nonconservative timing results. On a functional block from an industrial 65nm microprocessor, our algorithm produced a maximum pessimism reduction of 11.18% of cycle time over converged timing filtering analysis that does not consider logic constraints.
Debasish Das, Kip Killpack, Chandramouli V. Kashyap, Abhijit Jas, Hai Zhou 0001
ASP-DAC1
2008 Reducing Need for Collocated Ground and Satellite based Observations in Statistical Aerosol Optical Depth Estimation
abstract
One of the biggest challenges of current climate research is to characterize and quantify the effect of aerosols on the global and local weather. This requires an accurate prediction of aerosol optical density (AOD) which is defined as the amount of loss a beam of light incurs when it passes through the atmosphere. In this paper a neural network-based data-driven prediction model is considered which uses collocated satellite (MODIS) observation and ground-based (AERONET) AOD retrievals as predictors and target respectively. This paper studies an active learning-based data collection method which will facilitate the learning of a sufficiently accurate AOD prediction model using a minimal set of labeled training data by querying the labels of only the most informative data points.
Debasish Das, Vladan Radosavljevic, Slobodan Vucetic, Zoran Obradovic
IGARSS (2)1
2007 NostraXtalk: a predictive framework for accurate static timing analysis in udsm vlsi circuits
abstract
This paper presents a predictive framework for accurate static timing analysis in UDSM VLSI circuits. As technology scales to smaller dimensions, coupling capacitances are becoming a critical factor in signal integrity analysis. Coupling capacitances contribute to the noise and play a seminalrole in determining the timing windows of a circuit. Accuratean alysis of coupling effects is indispensable for meaning fulstatic timing and signal integrity analysis. Our proposed framework presents a Directed Search technique to calculate accurate coupling effects. We performed experiments on theISCAS'85 benchmarks and present the accuracy improvement up-to 45.5% compared to existing approaches. We also show that our framework decreased cell delay look-uptable accesses up-to 64.8%. Our results present the coupling effect on static timing analysis.
Debasish Das, Ahmed Shebaita, Yehea I. Ismail, Hai Zhou 0001, Kip Killpack
ACM Great Lakes Symposium on VLSI1
2007 Gate sizing by Lagrangian relaxation revisited
abstract
In this paper, we formulate the generalized convex sizing (GCS) problem that unifies and generalizes the sizing problems. We revisit the approach to solve the sizing problem by Lagrangian relaxation, point out several misunderstandings in the previous works, and extend the approach to handle general convex delay functions in the GCS problems. We identify a class of proper GCS problems whose objective functions in the simplified dual problem are differentiable and show many practical sizing problems, including the simultaneous sizing and clock skew optimization problem, are proper. We design an algorithm based on the method of feasible directions to solve proper GCS problems. The algorithm will provide evidences for infeasible GCS problems according to a condition derived by us. Experimental results confirm the efficiency and the effectiveness of our algorithm when the Elmore delay model is used.
Jia Wang 0003, Debasish Das, Hai Zhou 0001
ICCAD2
2006 FA-STAC: A Framework for Fast and Accurate Static Timing Analysis with Coupling
abstract
This paper presents a framework for fast and accurate static timing analysis considering coupling. With technology scaling to smaller dimensions, the impact of coupling induced delay variations can no longer be ignored. Timing analysis considering coupling is iterative, and can have considerably larger run-times than a single pass approach. We propose a novel and accurate coupling delay model, and present techniques to increase the convergence rate of timing analysis when complex coupling models are employed. Experimental results obtained for the ISCAS benchmarks show promising accuracy improvements using our coupling model while an efficient iteration scheme shows significant speedup (up to 62.1%) in comparison to traditional approaches.
Debasish Das, Ahmed Shebaita, Hai Zhou 0001, Yehea I. Ismail, Kip Killpack
ICCD1
2005 Hierarchical LUT structures for leakage power reduction (abstract only)
abstract
Reconfigurable technologies have made remarkable progress in the last few years. However, due to the overhead of programmability along with improved system capabilities, power dissipation has become one of the major concerns for designers. Moreover, with the trends in technology scaling, overall leakage power consumption is increasing alarmingly. In this work, we propose a leakage power optimization technique using look-up tables (LUTs) for SRAM-based FPGAs. Analysis of a set of 20 MCNC benchmarks using 4-input LUTs show that on an average only 53% of these LUTs use all their inputs. Based on this observation, we shut down SRAM cells and certain transistors associated with the unused inputs by employing hierarchical look-up tables, which can yield LUTs with varying number of inputs within the same logic block. We effectively utilize a Vdd gating scheme to cut-off power supply to one half or three quarters of the original 4-input LUT, which in turn yields a 3-input LUT or a 2-input LUT from a 4-input LUT respectively. Our experiments show that for 180 nm technology logic block leakage power savings is 22.9% on an average for the set of 20 MCNC benchmarks. This saving will be even higher for technologies 90 nm and smaller.
Somsubhra Mondal, Seda Ogrenci Memik, Debasish Das
FPGA3
1999 A New Network Topology with Multiple Meshes
abstract
This paper introduces a new network topology, called Multi-Mesh (MM), which uses multiple meshes as the basic building blocks interconnected in a suitable manner. The proposed network consists of n/sup 4/ processors and is 4-regular with a diameter of 2n. The network also contains a Hamiltonian cycle. Simple routing algorithms for point-to-point communication, one-to-all broadcast, and multicast have been described for this network. It is shown that a simple n/sup 2//spl times/n/sup 2/ mesh can also be emulated on this network in O(1) time. Several application examples have been discussed for which this network is found to be more efficient with regard to computational time than the corresponding mesh with the same number of processors. As examples, O(n) time algorithms for finding the sum, average, minimum, and maximum of n/sup 4/ data values, located at n/sup 4/ different processors have been discussed. Time-efficient implementations of algorithms for solving nontrivial problems, e.g., Lagrange's interpolation, matrix transposition, matrix multiplication, and Discrete Fourier Transform (DFT) computation have also been discussed. The time complexity of Lagrange's interpolation on this network is O(n) for n/sup 2/ data points compared to O(n/sup 2/) time on mesh of the same size. Matrix transpose requires O(n/sup 0.5/) time for an n/spl times/n. matrix. The time for multiplying two n/spl times/n matrices is O(n/sup 0.6/) with an AT-cost of O(n/sup 3/). DFT of n sample points can be computed in O(n/sup 0.6/) time on this network. The previous papers show that n/sup 4/ data elements can be sorted on this network in O(n) time.
Debasish Das, Mallika De, Bhabani P. Sinha
IEEE Trans. Computers1
1997 An Efficient Sorting Algorithm on the Multi-Mesh Network
abstract
The shear-sort algorithm on an SIMD mesh model requires 4/spl radic/N+o(/spl radic/N) time for sorting N elements arranged on a /spl radic/N/spl times//spl radic/N mesh. In this paper, we present an algorithm for sorting N elements in time O(N/sup 1/4/) on an SIMD multi-mesh architecture, thereby significantly improving the order of the time complexity. The multi-mesh architecture is built around n/sup 2/ blocks, where each block is an n/spl times/n mesh with n=N/sup 1/4/, so that each processor will uniformly have four neighbors in the final topology.
Mallika De, Debasish Das, Mabhin Ghosh, Bhabani P. Sinha
IEEE Trans. Computers2
1996 The generalized hypercube-connected-cycle: an efficient network topology
abstract
A new family of interconnection network, called Generalized Hypercube-Connected-Cycle (GHCC), is proposed. The topology is defined with two integer parameters l and m such that the total number of nodes N=lm/sup l/, degree of each node /spl delta/=m+1. The diameter D=[5l/2]-2, when l/spl ges/4, m/spl ne/1 and D=[5l/2]-1 when l/spl les/3 m/spl ne/1. The topology offers a design flexibility in the sense that out of the three design parameters N, /spl delta/ and D, any two can be chosen independently. The network graph is node symmetric, (m+1)-connected and also it provides a simple routing scheme. Implementation of the ASCEND and DESCEND classes of algorithms on this topology has also been described.
Srabani Sen Gupta, Debasish Das, Bhabani P. Sinha
HiPC2
1995 Implementation of Four Common Functions on an LNS Co-Processor
abstract
We propose a scheme for evaluating four commonly used functions namely, (1) inverse trigonometric functions, (2) trigonometric functions, (3) the exponential function, and (4) the logarithmic function with the help of a logarithmic number system (LNS) processor. A novel idea of series folding has been introduced for computing the above functions, expressed in the form of infinite series. We also show that with a suitable choice of the radix for the LNS we can evaluate exponential and logarithmic functions without using any extra hardware.>
Debasish Das, Krishnendu Mukhopadhyaya, Bhabani P. Sinha
IEEE Trans. Computers1