The high-density server is featured as low power, low volume, and high computational density. With the rising use of high-density servers in data-intensive and large-scale web applications, it requires a high-performa...The high-density server is featured as low power, low volume, and high computational density. With the rising use of high-density servers in data-intensive and large-scale web applications, it requires a high-performance and cost-efficient intra-server interconnection network. Most of state-of-the-art high-density servers adopt the fully-connected intra-server network to attain high network performance. Unfortunately, this solution costs too much due to the high degree of nodes. In this paper, we exploit the theoretically optimized Moore graph to interconnect the chips within a server. Accounting for the suitable size of applications, a 50-size Moore graph, called Hoffman-Singleton graph, is adopted. In practice, multiple chips should be integrated onto one processor board, which means that the original graph should be partitioned into homogeneous connected subgraphs. However, the existing partition scheme does not consider above problem and thus generates heterogeneous subgraphs. To address this problem, we propose two equivalent-partition schemes for the Hoffman-Singleton graph. In addition, a logic-based and minimal routing mechanism, which is both time and area efficient, is proposed. Finally, we compare the proposed network architecture with its counterparts, namely the fully-connected, Kautz and Torus networks. The results show that our proposed network can achieve competitive performance as fully-connected network and cost close to Torus.展开更多
The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation al...The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation algorithm for any 2-colorable graph is presented.An improved 7/5-approximation algorithm is then designed for a tree.The theoretical proof of the improved algorithm performance ratio is constructive,thus providing an explicit partition approach for each case according to the cardinality of two color classes.展开更多
Observability is a fundamental property of a partially observed dynamical system,which means whether one can use an input sequence and the corresponding output sequence to determine the initial state.Observability pro...Observability is a fundamental property of a partially observed dynamical system,which means whether one can use an input sequence and the corresponding output sequence to determine the initial state.Observability provides bases for many related problems,such as state estimation,identification,disturbance decoupling,controller synthesis,etc.Until now,fundamental improvement has been obtained in observability of Boolean control networks(BCNs)mainly based on two methods-Edward F.Moore's partition and our observability graph or their equivalent representations found later based on the semitensor product(STP)of matrices(where the STP was proposed by Daizhan Cheng),including necessary and sufficient conditions for different types of observability,extensions to probabilistic Boolean networks(PBNs)and singular BCNs,even to nondeterministic finite-transition systems(NFTSs);and the development(with the help of the STP of matrices)in related topics,such as com-putation of smallest invariant dual subspaces of BNs containing a set of Boolean functions,multiple-experiment observability verification/decomposition in BCNs,disturbance decoupling in BCNs,etc.This paper provides a thorough survey for these topics.The contents of the paper are guided by the above two methods.First,we show that Moore's partition-based method closely relates the following problems:computation of smallest invariant dual subspaces of BNs,multiple-experiment observ-ability verification/decomposition in BCNs,and disturbance decoupling in BCNs.However,this method does not apply to other types of observability or nondeterministic systems.Second,we show that based on our observability graph,four different types of observability have been verified in BCNs,verification results have also been extended to PBNs,singular BCNs,and NFTSs.In addition,Moore's partition also shows similarities between BCNs and linear time-invariant(LTI)control systems,e.g.,smallest invariant dual subspaces of BNs containing a set of Boolean functions in BCNs vs unobservable subspaces 展开更多
Let G =（V, E） be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m;（G） be the minimum of qe（V;） + pe（V;） over partitions V = V;∪ V;, where e（V;） denotes the number of edges spanned by V;. We sh...Let G =（V, E） be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m;（G） be the minimum of qe（V;） + pe（V;） over partitions V = V;∪ V;, where e（V;） denotes the number of edges spanned by V;. We show that if m;（G） = pqm-δ, then there exists a bipartition V;, V;of G such that e（V;） ≤ p;m-δ + p（m/2）;+ o（√m） and e（V;） ≤ q;m-δ + q（m/2）;+ o（√m） for δ = o(m;). This is sharp for com;lete graphs up to the error term o（√m）. For an integer k ≥ 2, let fk（G） denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk（G） =（1-1/k）m + α,then G admits a k-partition such that each vertex class spans at most m/k;-Ω(m/k;) edges forα = Ω（m/k;）. Both of the above im;rove the results of Bollob′as and Scott.展开更多
When a 3D model is transmitted over a lossy network, some model information may inevitably be missing. Under such situation, one may not be able to visualize the receiving model unless the lost model information has b...When a 3D model is transmitted over a lossy network, some model information may inevitably be missing. Under such situation, one may not be able to visualize the receiving model unless the lost model information has been retransmitted. Progressive model transmission offers an alternative to avoid the ＂all or nothing situation＂ by allowing a model to be visualized with a degraded quality when only part of the model data has been received. Unfortunately, in case some model refinement information is missing, one may still need to wait for such information to be retransmitted before the model can be rendered with a desired visual quality. To address this problem, we have developed a novel error resilient packetization scheme. We first construct a Non-Redundant Directed Acyclic Graph to encode the dependencies among the vertex splits of a progressive mesh. A special Global Graph Equipartition Packing Algorithm is then applied to partitioning this graph into several equal size sub-graphs, which is packed as packets. The packing algorithm comprises two main phases： initial partition phase and global refinement phase. Experimental results demonstrate that the proposed scheme can minimize the dependencies between packets. Hence, it reduces the delay in rendering 3D models with proper quality at the clients.展开更多
In the course of high-level synthesis of integrate circuit, the hard-to-test structure caused by irrational schedule and allocation reduces the testability of circuit. In order to improve the circuit testability, this...In the course of high-level synthesis of integrate circuit, the hard-to-test structure caused by irrational schedule and allocation reduces the testability of circuit. In order to improve the circuit testability, this paper proposes a weighted compatibility graph (WCG), which provides a weighted formula of compatibility graph based on register allocation for testability and uses improved weighted compatibility clique partition algorithm to deal with this WCG. As a result, four rules for testability are considered simultaneously in the course of register allocation so that the objective of improving the design of testability is acquired. Tested by many experimental results of benchmarks and compared with many other models, the register allocation algorithm proposed in this paper has greatly improved the circuit testability with little overhead on the final circuit area.展开更多
This paper addresses the leader selection problem for strong structural controllability(SSC)of multi-agent systems(MASs). For a path-bud graph, it is proved that only one leader is required to guarantee the SSC of MAS...This paper addresses the leader selection problem for strong structural controllability(SSC)of multi-agent systems(MASs). For a path-bud graph, it is proved that only one leader is required to guarantee the SSC of MASs. For a special type of topologies, based on the partition of the topology into disjoint pathes and path-buds, it is proved that the MASs is strongly structurally controllable if the root nodes of the pathes are selected as leaders. For general topologies, an algorithm is provided to determine the agents that can behave as leaders. For some special topologies, the minimum number of leaders guaranteeing the robust strong structural controllability(RSSC) of MASs is also obtained.Two examples are given to verify the effectiveness of the results.展开更多
Let G be a graph, let s be a positive integer, and let X be a subset of V(G). Denote δ(X) to be the minimum degree of the subgraph G[X] induced by X. A partition(X, Y) of V(G) is called s-good if min{δ(X), δ(Y)} s....Let G be a graph, let s be a positive integer, and let X be a subset of V(G). Denote δ(X) to be the minimum degree of the subgraph G[X] induced by X. A partition(X, Y) of V(G) is called s-good if min{δ(X), δ(Y)} s. In this paper, we strengthen a result of Maurer and a result of Arkin and Hassin, and prove that for any positive integer k with 2 k |V(G)|- 2, every connected graph G with δ(G) 2 admits a1-good partition(X, Y) such that |X| = k and |Y| = |V(G)|- k, and δ(X) + δ(Y) δ(G)- 1.展开更多
Mobile edge computing(MEC)is a promising technology for the Internet of Vehicles,especially in terms of application offloading and resource allocation.Most existing offloading schemes are sub-optimal,since these offlo...Mobile edge computing(MEC)is a promising technology for the Internet of Vehicles,especially in terms of application offloading and resource allocation.Most existing offloading schemes are sub-optimal,since these offloading strategies consider an application as a whole.In comparison,in this paper we propose an application-centric framework and build a finer-grained offloading scheme based on application partitioning.In our framework,each application is modelled as a directed acyclic graph,where each node represents a subtask and each edge represents the data flow dependency between a pair of subtasks.Both vehicles and MEC server within the communication range can be used as candidate offloading nodes.Then,the offloading involves assigning these computing nodes to subtasks.In addition,the proposed offloading scheme deal with the delay constraint of each subtask.The experimental evaluation show that,compared to existing non-partitioning offloading schemes,this proposed one effectively improves the performance of the application in terms of execution time and throughput.展开更多
An(s,t)-partition of a graph G=(V,E)is a partition of V=V 1∪V 2 suchthatδ(G[V_(1)])≥s andδ(G[V_(2)])≥t.Ithasbeenconjecturedthat,forsufficiently large n,every d-regular graph of order n has a(d/2,d/2)-partition(ca...An(s,t)-partition of a graph G=(V,E)is a partition of V=V 1∪V 2 suchthatδ(G[V_(1)])≥s andδ(G[V_(2)])≥t.Ithasbeenconjecturedthat,forsufficiently large n,every d-regular graph of order n has a(d/2,d/2)-partition(called an internal partition).Inthispaper,weprovethateveryd-regulargraphofordern hasa(d/2,d/2)partition(called a weak internal partition)for d≤9 and sufficiently large n.展开更多
This paper discusses the compile time task scheduling of parallel program running on cluster of SMP workstations. Firstly, the problem is stated formally and transformed into a graph parti-tion problem and proved to b...This paper discusses the compile time task scheduling of parallel program running on cluster of SMP workstations. Firstly, the problem is stated formally and transformed into a graph parti-tion problem and proved to be NP-Complete. A heuristic algorithm MMP-Solver is then proposed to solve the problem. Experiment result shows that the task scheduling can reduce communication over-head of parallel applications greatly and MMP-Solver outperforms the existing algorithms.展开更多
Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott(2005)asked the following natural question:What is the maximum c...Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott(2005)asked the following natural question:What is the maximum constant cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_(3-i))denotes the number of arcs in D from V_i to V_(3-i).Lee et al.(2016)conjectured that every directed graph D with m arcs and minimum outdegree at least d 2 admits a bipartition V(D)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-1))+o(1))m.In this paper,we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.展开更多
基金supported by the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No.XDA06010401the National Natural Science Foundation of China under Grant Nos.61202056,61331008,61221062the HuaweiResearch Program of China under Grant No.YBCB2011030
文摘The high-density server is featured as low power, low volume, and high computational density. With the rising use of high-density servers in data-intensive and large-scale web applications, it requires a high-performance and cost-efficient intra-server interconnection network. Most of state-of-the-art high-density servers adopt the fully-connected intra-server network to attain high network performance. Unfortunately, this solution costs too much due to the high degree of nodes. In this paper, we exploit the theoretically optimized Moore graph to interconnect the chips within a server. Accounting for the suitable size of applications, a 50-size Moore graph, called Hoffman-Singleton graph, is adopted. In practice, multiple chips should be integrated onto one processor board, which means that the original graph should be partitioned into homogeneous connected subgraphs. However, the existing partition scheme does not consider above problem and thus generates heterogeneous subgraphs. To address this problem, we propose two equivalent-partition schemes for the Hoffman-Singleton graph. In addition, a logic-based and minimal routing mechanism, which is both time and area efficient, is proposed. Finally, we compare the proposed network architecture with its counterparts, namely the fully-connected, Kautz and Torus networks. The results show that our proposed network can achieve competitive performance as fully-connected network and cost close to Torus.
基金gment This work was supported by the National Natural Science Foundation of China(No.11971139)the Natural Science Foundation of Zhejiang Province(No.LY21A010014)the Fundamental Research Funds for the Provincial Universities of Zhejiang(No.GK22990929900)。
文摘The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation algorithm for any 2-colorable graph is presented.An improved 7/5-approximation algorithm is then designed for a tree.The theoretical proof of the improved algorithm performance ratio is constructive,thus providing an explicit partition approach for each case according to the cardinality of two color classes.
文摘Observability is a fundamental property of a partially observed dynamical system,which means whether one can use an input sequence and the corresponding output sequence to determine the initial state.Observability provides bases for many related problems,such as state estimation,identification,disturbance decoupling,controller synthesis,etc.Until now,fundamental improvement has been obtained in observability of Boolean control networks(BCNs)mainly based on two methods-Edward F.Moore's partition and our observability graph or their equivalent representations found later based on the semitensor product(STP)of matrices(where the STP was proposed by Daizhan Cheng),including necessary and sufficient conditions for different types of observability,extensions to probabilistic Boolean networks(PBNs)and singular BCNs,even to nondeterministic finite-transition systems(NFTSs);and the development(with the help of the STP of matrices)in related topics,such as com-putation of smallest invariant dual subspaces of BNs containing a set of Boolean functions,multiple-experiment observability verification/decomposition in BCNs,disturbance decoupling in BCNs,etc.This paper provides a thorough survey for these topics.The contents of the paper are guided by the above two methods.First,we show that Moore's partition-based method closely relates the following problems:computation of smallest invariant dual subspaces of BNs,multiple-experiment observ-ability verification/decomposition in BCNs,and disturbance decoupling in BCNs.However,this method does not apply to other types of observability or nondeterministic systems.Second,we show that based on our observability graph,four different types of observability have been verified in BCNs,verification results have also been extended to PBNs,singular BCNs,and NFTSs.In addition,Moore's partition also shows similarities between BCNs and linear time-invariant(LTI)control systems,e.g.,smallest invariant dual subspaces of BNs containing a set of Boolean functions in BCNs vs unobservable subspaces
基金Supported by NSFC(Grant No.11671087)New Century Programming of Fujian Province(Grant No.JA14028)
文摘Let G =（V, E） be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m;（G） be the minimum of qe（V;） + pe（V;） over partitions V = V;∪ V;, where e（V;） denotes the number of edges spanned by V;. We show that if m;（G） = pqm-δ, then there exists a bipartition V;, V;of G such that e（V;） ≤ p;m-δ + p（m/2）;+ o（√m） and e（V;） ≤ q;m-δ + q（m/2）;+ o（√m） for δ = o(m;). This is sharp for com;lete graphs up to the error term o（√m）. For an integer k ≥ 2, let fk（G） denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk（G） =（1-1/k）m + α,then G admits a k-partition such that each vertex class spans at most m/k;-Ω(m/k;) edges forα = Ω（m/k;）. Both of the above im;rove the results of Bollob′as and Scott.
基金Supported by the National Natural Science Foundation of China under Grant No. 60533080the National Research Foundation for Doctoral Program of Higher Education of China Under Grant No. 20060335111.
文摘When a 3D model is transmitted over a lossy network, some model information may inevitably be missing. Under such situation, one may not be able to visualize the receiving model unless the lost model information has been retransmitted. Progressive model transmission offers an alternative to avoid the ＂all or nothing situation＂ by allowing a model to be visualized with a degraded quality when only part of the model data has been received. Unfortunately, in case some model refinement information is missing, one may still need to wait for such information to be retransmitted before the model can be rendered with a desired visual quality. To address this problem, we have developed a novel error resilient packetization scheme. We first construct a Non-Redundant Directed Acyclic Graph to encode the dependencies among the vertex splits of a progressive mesh. A special Global Graph Equipartition Packing Algorithm is then applied to partitioning this graph into several equal size sub-graphs, which is packed as packets. The packing algorithm comprises two main phases： initial partition phase and global refinement phase. Experimental results demonstrate that the proposed scheme can minimize the dependencies between packets. Hence, it reduces the delay in rendering 3D models with proper quality at the clients.
基金the National Natural Science Foundation of China (No.60273081)
文摘In the course of high-level synthesis of integrate circuit, the hard-to-test structure caused by irrational schedule and allocation reduces the testability of circuit. In order to improve the circuit testability, this paper proposes a weighted compatibility graph (WCG), which provides a weighted formula of compatibility graph based on register allocation for testability and uses improved weighted compatibility clique partition algorithm to deal with this WCG. As a result, four rules for testability are considered simultaneously in the course of register allocation so that the objective of improving the design of testability is acquired. Tested by many experimental results of benchmarks and compared with many other models, the register allocation algorithm proposed in this paper has greatly improved the circuit testability with little overhead on the final circuit area.
基金supported by the National Natural Science Foundation of China under Grant Nos.61573105,61473081,61273110the Natural Science Foundation of Jiangsu Province under Grant No.BK20141341
文摘This paper addresses the leader selection problem for strong structural controllability(SSC)of multi-agent systems(MASs). For a path-bud graph, it is proved that only one leader is required to guarantee the SSC of MASs. For a special type of topologies, based on the partition of the topology into disjoint pathes and path-buds, it is proved that the MASs is strongly structurally controllable if the root nodes of the pathes are selected as leaders. For general topologies, an algorithm is provided to determine the agents that can behave as leaders. For some special topologies, the minimum number of leaders guaranteeing the robust strong structural controllability(RSSC) of MASs is also obtained.Two examples are given to verify the effectiveness of the results.
基金supported by National Natural Science Foundation of China(Grant Nos.11201156,11331003 and 11171160)Natural Science Foundation of Jiangsu Province(Grant No.BK20131357)+1 种基金the Doctoral Fund of Ministry of Education of Chinaa project funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions
文摘Let G be a graph, let s be a positive integer, and let X be a subset of V(G). Denote δ(X) to be the minimum degree of the subgraph G[X] induced by X. A partition(X, Y) of V(G) is called s-good if min{δ(X), δ(Y)} s. In this paper, we strengthen a result of Maurer and a result of Arkin and Hassin, and prove that for any positive integer k with 2 k |V(G)|- 2, every connected graph G with δ(G) 2 admits a1-good partition(X, Y) such that |X| = k and |Y| = |V(G)|- k, and δ(X) + δ(Y) δ(G)- 1.
基金This work was supported by the National Natural Science Foundation of China(Grant Nos.U20A20177,61772377,91746206)the Fundamental Research Funds for the Central Universities,and Science and Technology planning project of ShenZhen(JCYJ20170818112550194).
文摘Mobile edge computing(MEC)is a promising technology for the Internet of Vehicles,especially in terms of application offloading and resource allocation.Most existing offloading schemes are sub-optimal,since these offloading strategies consider an application as a whole.In comparison,in this paper we propose an application-centric framework and build a finer-grained offloading scheme based on application partitioning.In our framework,each application is modelled as a directed acyclic graph,where each node represents a subtask and each edge represents the data flow dependency between a pair of subtasks.Both vehicles and MEC server within the communication range can be used as candidate offloading nodes.Then,the offloading involves assigning these computing nodes to subtasks.In addition,the proposed offloading scheme deal with the delay constraint of each subtask.The experimental evaluation show that,compared to existing non-partitioning offloading schemes,this proposed one effectively improves the performance of the application in terms of execution time and throughput.
基金supported by NNSF of China(No.11671376)the Fundamental Research Funds for the Central Universities.
文摘An(s,t)-partition of a graph G=(V,E)is a partition of V=V 1∪V 2 suchthatδ(G[V_(1)])≥s andδ(G[V_(2)])≥t.Ithasbeenconjecturedthat,forsufficiently large n,every d-regular graph of order n has a(d/2,d/2)-partition(called an internal partition).Inthispaper,weprovethateveryd-regulargraphofordern hasa(d/2,d/2)partition(called a weak internal partition)for d≤9 and sufficiently large n.
基金This work was supported by the National Natural Science Foundation of China (Grant No. 69933020) the "973" Program (Grant No. G1999032702).
文摘This paper discusses the compile time task scheduling of parallel program running on cluster of SMP workstations. Firstly, the problem is stated formally and transformed into a graph parti-tion problem and proved to be NP-Complete. A heuristic algorithm MMP-Solver is then proposed to solve the problem. Experiment result shows that the task scheduling can reduce communication over-head of parallel applications greatly and MMP-Solver outperforms the existing algorithms.
基金supported by National Natural Science Foundation of China (Grant No. 11671087)supported by National Science Foundation of USA (Grant No. DMS1600738)+2 种基金the Hundred Talents Program of Fujian Provincesupported by the Shandong Provincial Natural Science Foundation of China (Grant No. ZR2014JL001)the Excellent Young Scholars Research Fund of Shandong Normal University of China
文摘Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott(2005)asked the following natural question:What is the maximum constant cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_(3-i))denotes the number of arcs in D from V_i to V_(3-i).Lee et al.(2016)conjectured that every directed graph D with m arcs and minimum outdegree at least d 2 admits a bipartition V(D)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-1))+o(1))m.In this paper,we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.
