Qualification: 
Ph.D, MPhil, MSc
s_sundaram(at)cb.amrita.edu

Dr. Somasundaram K. currently serves as Professor and Chairperson in the Department of Mathematics, School of Engineering, Coimbatore Campus. His areas of research include Multilinear Algebra, Graph Theory, Graph Theory Algorithms in Network on Chip.

Publications

Publication Type: Journal Article

Year of Publication Publication Type Title

2018

Journal Article

J. Geetha and Dr. Somasundaram K., “Total Colorings of Product Graphs”, Graphs and Combinatorics (2018), vol. 34, no. 2, pp. 339–347, 2018.[Abstract]


A total coloring of a graph is an assignment of colors to all the elements of the graph in such a way that no two adjacent or incident elements receive the same color. In this paper, we prove Behzad–Vizing conjecture for product graphs. In particular, we obtain the tight bound for certain classes of graphs.

More »»

2017

Journal Article

S. Mohan, Geetha, J., and Dr. Somasundaram K., “Total coloring of the corona product of two graphs”, AUSTRALASIAN JOURNAL OF COMBINATORICS, vol. 68, no. 1, pp. 15–22, 2017.

2016

Journal Article

P. Mohan, Dr. Somasundaram K., Dash, S. S., Das, S., and Bhaskar, M. A., “Design and evaluation of 3D NoC routers with quality-of-service (QoS) mechanism for multi-core systems”, Advances in Intelligent Systems and Computing, vol. 394, pp. 429-441, 2016.[Abstract]


The importance of on-chip communication interconnects was greatly highlighted with the advent of semiconductor technology at nanoscale domain. As the sizes of semiconductor features are reduced day by day, there occurred problems related to wiring. Network-on-Chip architectures are therefore implemented to overcome the wiring issues and have lately been considered as an important area for research. The communication on NoC is carried out in specific topologies by means of routers. In this paper, Partial Mesh of Grid topology (PMG) is considered. We use the Quality of Service (QoS) mechanism to minimize the area and power. PMG-based NoC will give minimum area and power and it reduces the high chances of redundant connections. Throughput and latency are analysed along with other parameters like packet loss ratio and jitter using network simulator NS-2. Area and power analyses are done using Synopsys Design Compiler and PrimeTime PX tool. Our experimental results show that the architecture with QoS mechanism gives a significant reduction in area and power when compared to Region-based Routing (RBR) mechanism. Moreover, the partial mesh of grid topology gives minimal latency and high throughput when compared to mesh of grid topology. © Springer India 2016.

More »»

2016

Journal Article

P. Subramanian and Dr. Somasundaram K., “Some Conjectures on Permanents of Doubly Stochastic Matrices”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 19, pp. 997-1011, 2016.[Abstract]


AbstractLet denote the set of all doubly stochastic matrices of order n. Foregger [3] raised a n question whether per per (A) holds for all and , where Jn is the n × n matrix with each entry equal to .But this inequality does not hold good for all matrices in general. In this paper, we consider the above inequality for subpermanents and we provide a sufficient condition for a matrix A ∈ Ωn to satisfy the inequality σk(fJn + (1−t)A) ≤ σk(A) for 0 ≤ t ≤ 1 and discuss the consequences of this inequality. More »»

2016

Journal Article

J. Geetha and Dr. Somasundaram K., “Total Chromatic Number and Some Topological Indices”, Electronic Notes in Discrete Mathematics, vol. 53, pp. 363 - 371, 2016.[Abstract]


Abstract The total chromatic number χ ″ ( G ) of G is the smallest number of colors needed to color all elements of G in such a way that no adjacent or incident elements get the same color. The harmonic index H ( G ) of a graph G is defined as the sum of the weights 2 d ( u ) + d ( v ) of all edges uv of G, where d ( u ) denotes the degree of the vertex u in G. In this paper, we show a relation between the total chromatic number and the harmonic index. Also, we give relations between total chromatic number and some topological indices of a graph. More »»

2016

Journal Article

S. Mohan, Geetha, J., and Dr. Somasundaram K., “Total Coloring of Certain Classes of Product Graphs”, Electronic Notes in Discrete Mathematics, vol. 53, pp. 173 - 180, 2016.[Abstract]


Abstract A total coloring of a graph is an assignment of colors to all the elements of the graph such that no two adjacent or incident elements receive the same color. In this paper, we prove the tight bound of Behzad and Vizing conjecture on total coloring for Compound graph of G and H, where G and H are any graphs. More »»

2015

Journal Article

Aa Gupta, Geetha, J., and Dr. Somasundaram K., “Total coloring algorithm for graphs”, Applied Mathematical Sciences, vol. 9, pp. 1297-1302, 2015.[Abstract]


A total coloring of a graph is an assignment of colors to all the elements of graph such that no two adjacent or incident elements receive the same color. Behzad and Vizing conjectured that for any graph G the following inequality holds: Δ(G)+1≤X′′(G)≤Δ(G)+2, where Δ(G) is the maximum degree of G. Total coloring algorithm is a NP-hard algorithm. In this paper, we give the total coloring algorithm for any graph and we discuss the complexity of the algorithm. © 2015 Aman Gupta, J. Geetha and K. Somasundaram.

More »»

2015

Journal Article

J. Geetha and Dr. Somasundaram K., “Total coloring of generalized sierpiński graphs”, Australasian Journal of Combinatorics, vol. 63, no. 1, pp. 58-69, 2015.[Abstract]


A total coloring of a graph is an assignment of colors to all the elements of the graph in such a way that no two adjacent or incident elements receive the same color. In this paper, we prove the tight bound of the Behzad and Vizing conjecture on total coloring for the generalized Sierpiński graphs of cycle graphs and hypercube graphs. We give a total coloring for the WK-recursive topology, which also gives the tight bound. © 2015,University of Queensland. All rights reserved.

More »»

2014

Journal Article

Na Viswanathan, Paramasivam, Kb, and Dr. Somasundaram K., “An optimised 3D topology for on-chip communications”, International Journal of Parallel, Emergent and Distributed Systems, vol. 29, no. 4, pp. 346-362, 2014.[Abstract]


Increasing system complexity, energy and device reliability, requirement of modular approach, structured layout, effective spatial reuse of resources, scalability and re-programmability have made network-on-chip (NoC) an obvious interconnection design alternative to the ubiquitous bus based on chip communication architecture in system-on-chip. Designing of a topology and its routing scheme plays a vital role in determining performance of any NoC architecture. In recent years, 3D stacked NoC architecture attracts added interest in NoC design as it offers improved performance and shorter global interconnect. In this paper, we have developed a partially, vertically interconnected 3D topology, namely 3D Recursive Network Topology (3D RNT) and prove that the topology has a Hamiltonian connectedness. We have developed deadlock-free routing algorithm for the 3D RNT topology. Also, we compare the performance of the 3D RNT with partially and fully connected 3D mesh topologies (3D PMT and 3D FMT) by conducting suitable experiments. The experiment results show that there is not much deviation in respect of the performance of the 3D RNT on comparing with 3D PMT and 3D FMT even though a number of vertical links are trimmed down to 75%, which is an encouraging outcome as far as design space is concerned. © 2013 © 2013 Taylor & Francis.

More »»

2014

Journal Article

Dr. Somasundaram K., Plosila, Jb, and Viswanathan, Nc, “Deadlock free routing algorithm for minimizing congestion in a Hamiltonian connected recursive 3D-NoCs”, Microelectronics Journal, vol. 45, pp. 989-1000, 2014.[Abstract]


Network on Chip (NoC) has been proposed as a solution for addressing the challenges in System on Chip (SoC) design. Designing a topology and its routing schemes are vital problems in a NoC. One of the major challenges that designers face today in 3D integration is how to route the data packets within a layer and across the layers in a scalable and efficient manner. In any 3D topology, minimizing the amount of data packet transmissions during the routing is still an open problem. Any efficient traditional routing schemes should avoid deadlocks and minimize network congestion from a source node to a destination node. In this paper, we propose a 3D recursive hyper graph Hamiltonian connected network and we propose a deadlock free routing algorithm to minimize congestion in the network. We show that the proposed topology outperforms the topology presented by Dubois et al. (Elevator-First: a Dealock-free distributed routing algorithm for vertically partially connected 3d-Nocs, IEEE Trans. Comput. 62(3) (2013) 609-615) [1] with respect to average network latency. Also, we analysis the delay bound of the switches for the proposed topology and 3D Partially connected Mesh Topology (PMT) and conclude that our topology performs better than 3D PMT. © 2014 Elsevier Ltd. More »»

2013

Journal Article

Na Viswanathan, Paramasivam, Kb, and Dr. Somasundaram K., “Performance comparison of 3D NoC topologies using network calculus”, Life Science Journal, vol. 10, pp. 4379-4385, 2013.[Abstract]


Nowadays, System-on-Chips (SoCs) designers are forced to integrate tens to hundreds of functional and storage blocks in a single die to implement emerging complex computation, multimedia and network services. The integration of huge degree of the blocks in a single die poses new challenge in designing the interconnect architecture of the blocks in SoCs. The traditional bus based interconnect infrastructure is ineffective as the number of the blocks increases more than ten. The packet based Network- on- Chip (NoC) is an obvious interconnect design alternative to the bus based on-chip communication architecture in SoCs. The advent of 3D NoC architecture attracts added interest as it offers improved performance and shorter global interconnect. Evolving an efficient 3D network topology and developing 3D routing scheme play a crucial role in determining the performance of 3D NoC interconnect architecture. In this paper, two 3D NoC topologies, namely 3D Recursive Network Topology (3D RNT) and 3D Modified Mesh Topology (3D MMT) are presented. End-to-end delay, switch buffer size and the influence of the buffer size in determining area overhead requirement of the two topologies are evaluated using an analytical model of network calculus and the evaluation results of the two topologies are compared. It is shown that the 3D RNT outperforms the 3D MMT even though 50% of the vertical links are trimmed down in the former topology. Further, 20 % reduction in average switch buffer size and 16% reduction in area overhead requirement are achieved in the 3D RNT. The results of the analysis are of use to evaluate and optimize 3D NoC interconnect architecture as far as the design space is concerned. More »»

2013

Journal Article

N. Viswanathan, Paramasivam, K., and Dr. Somasundaram K., “Performance and cost metrics analysis of a 3D NoC topology using network calculus”, Applied Mathematical Sciences, vol. 7, pp. 4173-4184, 2013.[Abstract]


The packet switching based Network-on-Chip (NoC) is an obvious interconnect design alternative to the shared bus, crossbar or ring based on-chip communication architecture used in System-on-Chips (SoCs). The advent of the three dimensional NoC (3D NoC) architecture attracts added interest as it offers improved performance and shorter global interconnect. In the 3D NoC architecture, topology plays a vital role in determining the performance of the interconnect architecture. The performance and cost metrics of the 3D NoC topology are evaluated by using simulation in general. However, analytical models provide more insights on how the traffic related parameters influence the performance of the topology. In this paper, the traffic related parameters of a 3D NoC topology, namely 3D Recursive Network Topology (3D RNT) are evaluated by using network calculus based methodology and the results of the evaluation are compared against the results produced using simulation. © 2013 N. Viswanathan et al.

More »»

2012

Journal Article

Na Viswanathan, Paramasivam, Kb, and Dr. Somasundaram K., “Exploring optimal topology and routing algorithm for 3D network on chip”, American Journal of Applied Sciences, vol. 9, pp. 300-308, 2012.[Abstract]


Problem statement: Network on Chip (NoC) is an appropriate candidate to implement interconnections in SoCs. Increase in number of IP blocks in 2D NoC will lead to increase in chip area, global interconnect, length of the communication channel, number of hops transversed by a packet, latency and difficulty in clock distribution. 3D NoC is evolved to overcome the drawbacks of 2D NoC. Topology, switching mechanism and routing algorithm are major area of 3D NoC research. In this study, three topologies (3D-MT, 3D-ST and 3D-RNT) and routing algorithm for 3D NoC are presented. Approach: Experiment is conducted to evaluate the performance of the topologies and routing algorithm. Evaluation parameters are latency, probability and network diameter and energy dissipation. Results: It is demonstrated by a comparison of experimental results analysis that 3D-RNT is a suitable candidate for 3D NoC topology. Conclusion: The performance of the topologies and routing algorithm for 3D NoC is analysed. 3D-MT is not a suitable candidate for 3D NoC, 3D-ST is a suitable candidate provided interlayer communications are frequent and 3D-RNT is a suitable candidate as interlayer communications are limited. © 2012 Science Publications. More »»

2012

Journal Article

Dr. Somasundaram K. and Plosila, Jc, “Deadlock free routing algorithm for minimizing data packet transmission in network on chip”, International Journal of Embedded and Real-Time Communication Systems, vol. 3, pp. 70-81, 2012.[Abstract]


Network on chip (NoC) has been proposed as a solution for addressing the design challenges of future high performance nanoscale architectures. In NoCs, the traditional routing schemes are routing packets through a single path or multiple paths from one source node to a destination node, minimizing the congestion in the routing architecture. Although these routing algorithms are moderately efficient, they are time dependent. To reduce overall data packet transmission time in the network, the authors consider a network with multiple sources and multiple destinations. Multi-dimensional routing problems appear naturally in several resource allocation problems, communication networks and wireless sensor networks. In this paper, the authors have constructed a deadlock-free multi-dimensional path routing algorithm for minimizing the congestion in NoC. More »»

2011

Journal Article

Dr. Somasundaram K. and Subramanian, P., “Determinantal Mates”, International Journal of Algebra, vol. 5, pp. 1181–1187, 2011.

2010

Journal Article

V. H. Prathyush and Dr. Somasundaram K., “Multi-level sequential circuit partitioning for test vector generation for low power test in VLSI”, International Journal of Engineering, Science and Technology, vol. 2, 2010.[Abstract]


Sequential graph partitioning algorithms have been developed to fulfill the requirements of emerging multi-phase problems in circuit testing models. In this paper, we present a multi-level graph partitioning algorithm for circuit partitioning, which will minimize the number of test vectors during a low power test in VLSI circuits. By reducing the number of test vectors, we can reduce the energy consumption during the test. Our experimental results with ISCAS bench mark circuits have shown that the power can be reduced up to 55%. More »»

2009

Journal Article

Dr. Somasundaram K., “Graph Mates”, Electronic Notes in Discrete Mathematics, vol. 33, pp. 37-41, 2009.[Abstract]


A weighted digraph graph D is said to be doubly stochastic if all the weights of the edges in D are in [0, 1] and sum of the weights of the edges incident to each vertex in D is one. Let Ω(G) be denoted as set of all doubly stochastic digraphs with n vertices. We defined a Graph Mates in Ω(G) and derived a necessary and sufficient condition for two doubly stochastic digraphs are to be a Graph Mates. © 2009 Elsevier B.V. All rights reserved. More »»

2008

Journal Article

SaMaria Arulraj and Dr. Somasundaram K., “Permanental Mates: Perturbations and Hwang's conjecture”, Applied Mathematics Letters, vol. 21, pp. 786-790, 2008.[Abstract]


Let Ωn denote the set of all n × n doubly stochastic matrices. Two unequal matrices A and B in Ωn are called permanental mates if the permanent function is constant on the line segment t A + (1 - t) B, 0 ≤ t ≤ 1, connecting A and B. We study the perturbation matrix A + E of a symmetric matrix A in Ωn as a permanental mate of A. Also we show an example to disprove Hwang's conjecture, which states that, for n ≥ 4, any matrix in the interior of Ωn has no permanental mate. © 2007 Elsevier Ltd. All rights reserved. More »»

2008

Journal Article

Dr. Somasundaram K. and Raj, S. M. Ab, “Permanent: Evaluation by parallel algorithm”, Journal of Information and Computing Science, vol. 3, no. 1, pp. 69-72, 2008.[Abstract]


Permanent of a matrix is # p - complete problem shown by many authors. In this paper we present a parallel algorithm for evaluation of permanent of an n × n matrix with multi processors. More »»

2007

Journal Article

Dr. Somasundaram K., “Multi-level Sequential circuit partitioning for delay minimization of VLSI circuits”, J. of Information and Computing Science, vol. 2, pp. 66–70, 2007.[Abstract]


Sequential graph partitioning algorithms have been developed to fulfill the requirements of emerging multi-phase problems in circuit delay models. In this paper we propose a heuristic algorithm for kpartition, which minimizes the circuit delay and cut size. Experimental results with MCNC benchmark circuits have shown that the delay in the circuit can be reduced by marginally in comparison with the other algorithms More »»

2007

Journal Article

S. Maria Arulraj and Dr. Somasundaram K., “Star Matrices: Properties And Conjectures”, Applied Mathematics E-Notes, vol. 7, pp. 42–49, 2007.[Abstract]


Let Ωn denote the set of all nxn doubly stochastic matrices. A matrix B ∈ Ωn is said to be a star matrix if per(αB + (1 − α)A) ≤ α perB + (1 − α)perA, for all A ∈ Ωn and for all α ∈ [0, 1]. In this paper we derive a necessary condition for a star matrix to be in Ωn, and a partial proof of the star conjecture: The direct sum of two star matrices is a star matrix. More »»

2006

Journal Article

Dr. Somasundaram K., “Graph Partitioning in VLSI Design and Testing: A Review”, Discrete Mathematics and Its Applications, p. 162, 2006.

Publication Type: Conference Proceedings

Year of Publication Publication Type Title

2014

Conference Proceedings

N. V. Anjali and Dr. Somasundaram K., “Design and evaluation of virtual channel router for mesh-of-grid based NoC”, International Conference on Electronics and Communication Systems (ICECS), 2014 . Coimbatore, 2014.[Abstract]


Network on Chips (NoCs) has now replaced the bus based architectures for communication between different cores in a multiprocessor System on Chip (SoC). NoC integrates SoCs in a better manner. It has the advantage of good scalability and high bandwidth. The communication on NoC is carried out by means of routers. Routers are the back bone of NoC. The design of routers is different for different topologies. In this paper, a Mesh-of-Grid topology is considered. A virtual channel router for mesh of grid topology of NoC is presented here. Area and Power is synthesized for the virtual channel router using Synopsys Design Vision. The experimental results show that the area and power will increase if the bit size of flit is increased.

More »»

2012

Conference Proceedings

Na Viswanathan, Paramasivam, Kb, and Dr. Somasundaram K., “Exploring hierarchical, cluster based 3D topologies for 3D NoC”, Procedia Engineering, vol. 30. Coimbatore, pp. 606-615, 2012.[Abstract]


Network-on-Chip (NoC) has been recognized as an effective solution for complex on-chip communication problems faced in System-on-Chips (SoCs). Network topology, switching mechanism and routing algorithms are the key research area in NoC. In recent years, since the inception of Through-Silicon-Vias (TSVs) to realize vertical channel, 3D stacked NoC architecture attracts a lot of interest as it offers improved performance and shorter global interconnect. In this paper, two clustered 3D network topologies (3D-ST and 3D-RNT) and hierarchical, cluster based routing algorithms are presented. Experimental results on various parameters like latency, drop probability and energy dissipation are compared for the two topologies. It is demonstrated from the analysis that 3D-RNT is an appropriate candidate for 3D NoC provided interlayer communications are not very frequent. More »»

Publication Type: Conference Paper

Year of Publication Publication Type Title

2011

Conference Paper

Na Viswanathan, Paramasivam, Kb, and Dr. Somasundaram K., “Performance analysis of cluster based 3D routing algorithms for NoC”, in 2011 IEEE Recent Advances in Intelligent Computational Systems, RAICS 2011, Trivandrum, Kerala, 2011, pp. 157-162.[Abstract]


In the nano scaled transistors integration era, interconnection of IP blocks and data exchange among the IP blocks are crucial concerns in System on Chip (SoC). Network-on-Chip (NoC) is an on-chip communication methodology proposed to resolve the increased interconnection problems in SoC. In deep sub-micron regime, 3D NoC becomes an emerging research area in recent years as the three dimensional (3D) integrated circuits (ICs) can offer shorter interconnection wire and dissipate lesser power. Major area of the 3D NoC research is network topology and routing techniques. In this paper, we present an NS-2 (Network Simulator) simulation environment for two 3D network topologies (GBT and CBT) and cluster based routing algorithms. Simulation results are reported. Simulation results about the relationship between switch buffer size, injected traffic load, packet delay, packet drop probability and energy dissipation are analyzed. On comparing CBT with GBT, a significant performance improvement is demonstrated. © 2011 IEEE. More »»

2009

Conference Paper

Dr. Somasundaram K. and Plosila, J., “Multi-dimensional routing algorithms for congestion minimization in Network-on-Chip”, in 2009 NORCHIP, 2009.[Abstract]


In network on chip (NoC), the traditional routing schemes are routing the network through a single path or multiple paths from one source node to a destination node, which will minimize the congestion in the routing architecture. Though these routing algorithms are moderately efficient, but time dependent. To reduce overall data packet transmission time in the network, we consider a network with multiple sources and multiple destinations. Multi-dimensional routing problems appear naturally in several resource allocation problems, communication networks and wireless sensor networks. In this paper, we have shown a multi-dimensional path routing algorithm for minimizing the congestion in NoC with deadlock free. More »»
207
PROGRAMS
OFFERED
5
AMRITA
CAMPUSES
15
CONSTITUENT
SCHOOLS
A
GRADE BY
NAAC, MHRD
8th
RANK(INDIA):
NIRF 2018
150+
INTERNATIONAL
PARTNERS