In traditional framework,mandatory access control(MAC) system and malicious software are run in kernel mode. Malicious software can stop MAC systems to be started and make it do invalid. This problem cannot be solved ...In traditional framework,mandatory access control(MAC) system and malicious software are run in kernel mode. Malicious software can stop MAC systems to be started and make it do invalid. This problem cannot be solved under the traditional framework if the operating system(OS) is comprised since malwares are running in ring 0 level. In this paper,we propose a novel way to use hypervisors to protect kernel integrity and the access control system in commodity operating systems. We separate the access control system into three parts: policy management(PM),security server(SS) and policy enforcement(PE). Policy management and the security server reside in the security domain to protect them against malware and the isolation feather of the hypervisor can protect them from attacks. We add an access vector cache(AVC) between SS and PE in the guest OS,in order to speed up communication between the guest OS and the security domain. The policy enforcement module is retained in the guest OS for performance. The security of AVC and PE can be ensured by using a memory protection mechanism. The goal of protecting the OS kernel is to ensure the security of the execution path. We implementthe system by a modified Xen hypervisor. The result shows that we can secure the security of the access control system in the guest OS with no overhead compared with modules in the latter. Our system offers a centralized security policy for virtual domains in virtual machine environments.Keywords: hypervisor; virtualization; memo-展开更多
Data race is one of the most important concurrent anomalies in multi-threaded programs.Emerging con-straint-based techniques are leveraged into race detection,which is able to find all the races that can be found by a...Data race is one of the most important concurrent anomalies in multi-threaded programs.Emerging con-straint-based techniques are leveraged into race detection,which is able to find all the races that can be found by any oth-er sound race detector.However,this constraint-based approach has serious limitations on helping programmers analyze and understand data races.First,it may report a large number of false positives due to the unrecognized dataflow propa-gation of the program.Second,it recommends a wide range of thread context switches to schedule the reported race(in-cluding the false one)whenever this race is exposed during the constraint-solving process.This ad hoc recommendation imposes too many context switches,which complicates the data race analysis.To address these two limitations in the state-of-the-art constraint-based race detection,this paper proposes DFTracker,an improved constraint-based race detec-tor to recommend each data race with minimal thread context switches.Specifically,we reduce the false positives by ana-lyzing and tracking the dataflow in the program.By this means,DFTracker thus reduces the unnecessary analysis of false race schedules.We further propose a novel algorithm to recommend an effective race schedule with minimal thread con-text switches for each data race.Our experimental results on the real applications demonstrate that 1)without removing any true data race,DFTracker effectively prunes false positives by 68%in comparison with the state-of-the-art constraint-based race detector;2)DFTracker recommends as low as 2.6-8.3(4.7 on average)thread context switches per data race in the real world,which is 81.6%fewer context switches per data race than the state-of-the-art constraint based race detec-tor.Therefore,DFTracker can be used as an effective tool to understand the data race for programmers.展开更多
Cloud is an emerging computing paradigm.It has drawn extensive attention from both academia and industry.But its security issues have been considered as a critical obstacle in its rapid development.When data owners st...Cloud is an emerging computing paradigm.It has drawn extensive attention from both academia and industry.But its security issues have been considered as a critical obstacle in its rapid development.When data owners store their data as plaintext in cloud,they lose the security of their cloud data due to the arbitrary accessibility,specially accessed by the un-trusted cloud.In order to protect the confidentiality of data owners’cloud data,a promising idea is to encrypt data by data owners before storing them in cloud.However,the straightforward employment of the traditional encryption algorithms can not solve the problem well,since it is hard for data owners to manage their private keys,if they want to securely share their cloud data with others in a fine-grained manner.In this paper,we propose a fine-grained and heterogeneous proxy re-encryption(FHPRE)system to protect the confidentiality of data owners’cloud data.By applying the FH-PRE system in cloud,data owners’cloud data can be securely stored in cloud and shared in a fine-grained manner.Moreover,the heterogeneity support makes our FH-PRE system more efficient than the previous work.Additionally,it provides the secure data sharing between two heterogeneous cloud systems,which are equipped with different cryptographic primitives.展开更多
Graph is a well known data structure to represent the associated relationships in a variety of applications,e.g.,data science and machine learning.Despite a wealth of existing efforts on developing graph processing sy...Graph is a well known data structure to represent the associated relationships in a variety of applications,e.g.,data science and machine learning.Despite a wealth of existing efforts on developing graph processing systems for improving the performance and/or energy efficiency on traditional architectures,dedicated hardware solutions,also referred to as graph processing accelerators,are essential and emerging to provide the benefits significantly beyond what those pure software solutions can offer.In this paper,we conduct a systematical survey regarding the design and implementation of graph processing accelerators.Specifically,we review the relevant techniques in three core components toward a graph processing accelerator:preprocessing,parallel graph computation,and runtime scheduling.We also examine the benchmarks and results in existing studies for evaluating a graph processing accelerator.Interestingly,we find that there is not an absolute winner for all three aspects in graph acceleration due to the diverse characteristics of graph processing and the complexity of hardware configurations.We finally present and discuss several challenges in details,and further explore the opportunities for the future research.展开更多
Non-Volatile Main Memories (NVMMs) have recently emerged as a promising technology for future memory systems. Generally, NVMMs have many desirable properties such as high density, byte-addressability, non-volatility, ...Non-Volatile Main Memories (NVMMs) have recently emerged as a promising technology for future memory systems. Generally, NVMMs have many desirable properties such as high density, byte-addressability, non-volatility, low cost, and energy efficiency, at the expense of high write latency, high write power consumption, and limited write endurance. NVMMs have become a competitive alternative of Dynamic Random Access Memory (DRAM), and will fundamentally change the landscape of memory systems. They bring many research opportunities as well as challenges on system architectural designs, memory management in operating systems (OSes), and programming models for hybrid memory systems. In this article, we revisit the landscape of emerging NVMM technologies, and then survey the state-of-the-art studies of NVMM technologies. We classify those studies with a taxonomy according to different dimensions such as memory architectures, data persistence, performance improvement, energy saving, and wear leveling. Second, to demonstrate the best practices in building NVMM systems, we introduce our recent work of hybrid memory system designs from the dimensions of architectures, systems, and applications. At last, we present our vision of future research directions of NVMMs and shed some light on design challenges and opportunities.展开更多
Data races are ubiquitous in multi-threaded ap- plications, but they are by no means easy to detect. One of the most important reasons is the complexity of thread in- terleavings. A volume of research has been devoted...Data races are ubiquitous in multi-threaded ap- plications, but they are by no means easy to detect. One of the most important reasons is the complexity of thread in- terleavings. A volume of research has been devoted to the interleaving-insensitive detection. However, all the previous work focuses on the uniform detection (unknown to the char- acteristics of thread interleavings), thereby making the detec- tion defective in either reporting false positives or suffering from prohibitive overhead. To cope with the problem above, we propose an efficient, precise, and sound step-by-step res- olution based on the characteristics of thread interleavings. We first try to tease apart the categories of thread interleav- ings from the several typical sources arising from the lock synchronizations. We then conduct a brief study and find a new and complex pattern the previous work cannot detect. It is also revealed that the simple pattern with the majority of thread interleavings can be resolved by a simple processing to achieve a big profit for the previous reordering-based design. Our final experimental results demonstrate the effectiveness of our empiricism-based approach, and show that 51.0% of execution time and 52.3 % of trace size arising from the state- of-the-art reordering technique can be saved through a quick filtering of the simple pattern with a negligible (4.45%) per- formance overhead introduced on-the-fly.展开更多
Entity linking refers to linking a string in a text to corresponding entities in a knowledge base through candidate entity generation and candidate entity ranking.It is of great significance to some NLP(natural langua...Entity linking refers to linking a string in a text to corresponding entities in a knowledge base through candidate entity generation and candidate entity ranking.It is of great significance to some NLP(natural language processing)tasks,such as question answering.Unlike English entity linking,Chinese entity linking requires more consideration due to the lack of spacing and capitalization in text sequences and the ambiguity of characters and words,which is more evident in certain scenarios.In Chinese domains,such as industry,the generated candidate entities are usually composed of long strings and are heavily nested.In addition,the meanings of the words that make up industrial entities are sometimes ambiguous.Their semantic space is a subspace of the general word embedding space,and thus each entity word needs to get its exact meanings.Therefore,we propose two schemes to achieve better Chinese entity linking.First,we implement an ngram based candidate entity generation method to increase the recall rate and reduce the nesting noise.Then,we enhance the corresponding candidate entity ranking mechanism by introducing sense embedding.Considering the contradiction between the ambiguity of word vectors and the single sense of the industrial domain,we design a sense embedding model based on graph clustering,which adopts an unsupervised approach for word sense induction and learns sense representation in conjunction with context.We test the embedding quality of our approach on classical datasets and demonstrate its disambiguation ability in general scenarios.We confirm that our method can better learn candidate entities’fundamental laws in the industrial domain and achieve better performance on entity linking through experiments.展开更多
Computer vision(CV)algorithms have been extensively used for a myriad of applications nowadays.As the multimedia data are generally well-formatted and regular,it is beneficial to leverage the massive parallel processi...Computer vision(CV)algorithms have been extensively used for a myriad of applications nowadays.As the multimedia data are generally well-formatted and regular,it is beneficial to leverage the massive parallel processing power of the underlying platform to improve the performances of CV algorithms.Single Instruction Multiple Data(SIMD)instructions,capable of conducting the same operation on multiple data items in a single instruction,are extensively employed to improve the efficiency of CV algorithms.In this paper,we evaluate the power and effectiveness of RISC-V vector extension(RV-V)on typical CV algorithms,such as Gray Scale,Mean Filter,and Edge Detection.By our examinations,we show that compared with the baseline OpenCV implementation using scalar instructions,the equivalent implementations using the RV-V(version 0.8)can reduce the instruction count of the same CV algorithm up to 24x,when processing the same input images.Whereas,the actual performances improvement measured by the cycle counts is highly related with the specific implementation of the underlying RV-V co-processor.In our evaluation,by using the vector co-processor(with eight execution lanes)of Xuantie C906,vector-version CV algorithms averagely exhibit up to 2.98x performances speedups compared with their scalar counterparts.展开更多
In modern computer systems, system event logs have always been the primary source for checking system status. As computer systems become more and more complex, the interaction between software and hardware increases f...In modern computer systems, system event logs have always been the primary source for checking system status. As computer systems become more and more complex, the interaction between software and hardware increases frequently. The components will generate enormous log information, including running reports and fault information. The sheer quantity of data is a great challenge for analysis relying on the manual method. In this paper, we implement a management and analysis system of log information, which can assist system administrators to understand the real-time status of the entire system, classify logs into different fault types, and determine the root cause of the faults. In addition, we improve the existing fault correlation analysis method based on the results of system log classification. We apply the system in a cloud computing environment for evaluation. The results show that our system can classify fault logs automatically and effectively. With the proposed system, administrators can easily detect the root cause of faults.展开更多
With the rapid growth of real-world graphs,the size of which can easily exceed the on-chip(board)storage capacity of an accelerator,processing large-scale graphs on a single Field Programmable Gate Array(FPGA)becomes ...With the rapid growth of real-world graphs,the size of which can easily exceed the on-chip(board)storage capacity of an accelerator,processing large-scale graphs on a single Field Programmable Gate Array(FPGA)becomes difficult.The multi-FPGA acceleration is of great necessity and importance.Many cloud providers(e.g.,Amazon,Microsoft,and Baidu)now expose FPGAs to users in their data centers,providing opportunities to accelerate large-scale graph processing.In this paper,we present a communication library,called FDGLib,which can easily scale out any existing single FPGA-based graph accelerator to a distributed version in a data center,with minimal hardware engineering efforts.FDGLib provides six APIs that can be easily used and integrated into any FPGA-based graph accelerator with only a few lines of code modifications.Considering the torus-based FPGA interconnection in data centers,FDGLib also improves communication efficiency using simple yet effective torus-friendly graph partition and placement schemes.We interface FDGLib into AccuGraph,a state-of-the-art graph accelerator.Our results on a 32-node Microsoft Catapult-like data center show that the distributed AccuGraph can be 2.32x and 4.77x faster than a state-of-the-art distributed FPGA-based graph accelerator ForeGraph and a distributed CPU-based graph system Gemini,with better scalability.展开更多
Real-world networks,such as social networks,cryptocurrency networks,and e-commerce networks,always have occurrence time of interactions between nodes.Such networks are typically modeled as temporal graphs.Mining cohes...Real-world networks,such as social networks,cryptocurrency networks,and e-commerce networks,always have occurrence time of interactions between nodes.Such networks are typically modeled as temporal graphs.Mining cohesive subgraphs from temporal graphs is practical and essential in numerous data mining applications,since mining cohesive subgraphs gets insights into the time-varying nature of temporal graphs.However,existing studies on mining cohesive subgraphs,such as Densest-Exact and k-truss,are mainly tailored for static graphs(whose edges have no temporal information).Therefore,those cohesive subgraph models cannot indicate both the temporal and the structural characteristics of subgraphs.To this end,we explore the model of cohesive temporal subgraphs by incorporating both the evolving and the structural characteristics of temporal subgraphs.Unfortunately,the volume of time intervals in a temporal network is quadratic.As a result,the time complexity of mining temporal cohesive subgraphs is high.To efficiently address the problem,we first mine the temporal density distribution of temporal graphs.Guided by the distribution,we can safely prune many unqualified time intervals with the linear time cost.Then,the remaining time intervals where cohesive temporal subgraphs fall in are examined using the greedy search.The results of the experiments on nine real-world temporal graphs indicate that our model outperforms state-of-the-art solutions in efficiency and quality.Specifically,our model only takes less than two minutes on a million-vertex DBLP and has the highest overall average ranking in EDB and TC metrics.展开更多
Many systems have been built to employ the delta-based iterative execution model to support iterative algorithms on distributed platforms by exploiting the sparse computational dependencies between data items of these...Many systems have been built to employ the delta-based iterative execution model to support iterative algorithms on distributed platforms by exploiting the sparse computational dependencies between data items of these iterative algorithms in a synchronous or asynchronous approach. However, for large-scale iterative algorithms, existing synchronous solutions suffer from slow convergence speed and load imbalance, because of the strict barrier between iterations;while existing asynchronous approaches induce excessive redundant communication and computation cost as a result of being barrier-free. In view of the performance trade-off between these two approaches, this paper designs an efficient execution manager, called Aiter-R, which can be integrated into existing delta-based iterative processing systems to efficiently support the execution of delta-based iterative algorithms, by using our proposed group-based iterative execution approach. It can efficiently and correctly explore the middle ground of the two extremes. A heuristic scheduling algorithm is further proposed to allow an iterative algorithm to adaptively choose its trade-off point so as to achieve the maximum efficiency. Experimental results show that Aiter-R strikes a good balance between the synchronous and asynchronous policies and outperforms state-of-the-art solutions. It reduces the execution time by up to 54.1% and 84.6% in comparison with existing asynchronous and the synchronous models, respectively.展开更多
Graph processing has been widely used in many scenarios,from scientific computing to artificial intelligence.Graph processing exhibits irregular computational parallelism and random memory accesses,unlike traditional ...Graph processing has been widely used in many scenarios,from scientific computing to artificial intelligence.Graph processing exhibits irregular computational parallelism and random memory accesses,unlike traditional workloads.Therefore,running graph processing workloads on conventional architectures(e.g.,CPUs and GPUs)often shows a significantly low compute-memory ratio with few performance benefits,which can be,in many cases,even slower than a specialized single-thread graph algorithm.While domain-specific hardware designs are essential for graph processing,it is still challenging to transform the hardware capability to performance boost without coupled software codesigns.This article presents a graph processing ecosystem from hardware to software.We start by introducing a series of hardware accelerators as the foundation of this ecosystem.Subsequently,the codesigned parallel graph systems and their distributed techniques are presented to support graph applications.Finally,we introduce our efforts on novel graph applications and hardware architectures.Extensive results show that various graph applications can be efficiently accelerated in this graph processing ecosystem.展开更多
基金supported by the National 973 Basic Research Program of China under grant No.2014CB340600the National Natural Science Foundation of China under grant No.61370230 and No.61662022+1 种基金Program for New Century Excellent Talents in University Under grant NCET-13-0241Natural Science Foundation of Huhei Province under Grant No.2016CFB371
文摘In traditional framework,mandatory access control(MAC) system and malicious software are run in kernel mode. Malicious software can stop MAC systems to be started and make it do invalid. This problem cannot be solved under the traditional framework if the operating system(OS) is comprised since malwares are running in ring 0 level. In this paper,we propose a novel way to use hypervisors to protect kernel integrity and the access control system in commodity operating systems. We separate the access control system into three parts: policy management(PM),security server(SS) and policy enforcement(PE). Policy management and the security server reside in the security domain to protect them against malware and the isolation feather of the hypervisor can protect them from attacks. We add an access vector cache(AVC) between SS and PE in the guest OS,in order to speed up communication between the guest OS and the security domain. The policy enforcement module is retained in the guest OS for performance. The security of AVC and PE can be ensured by using a memory protection mechanism. The goal of protecting the OS kernel is to ensure the security of the execution path. We implementthe system by a modified Xen hypervisor. The result shows that we can secure the security of the access control system in the guest OS with no overhead compared with modules in the latter. Our system offers a centralized security policy for virtual domains in virtual machine environments.Keywords: hypervisor; virtualization; memo-
基金This work is supported by the National Key Research and Development Program of China under Grant No.2023YFB4503400the National Natural Science Foundation of China under Grant Nos.62322205,62072195,and 61825202.
文摘Data race is one of the most important concurrent anomalies in multi-threaded programs.Emerging con-straint-based techniques are leveraged into race detection,which is able to find all the races that can be found by any oth-er sound race detector.However,this constraint-based approach has serious limitations on helping programmers analyze and understand data races.First,it may report a large number of false positives due to the unrecognized dataflow propa-gation of the program.Second,it recommends a wide range of thread context switches to schedule the reported race(in-cluding the false one)whenever this race is exposed during the constraint-solving process.This ad hoc recommendation imposes too many context switches,which complicates the data race analysis.To address these two limitations in the state-of-the-art constraint-based race detection,this paper proposes DFTracker,an improved constraint-based race detec-tor to recommend each data race with minimal thread context switches.Specifically,we reduce the false positives by ana-lyzing and tracking the dataflow in the program.By this means,DFTracker thus reduces the unnecessary analysis of false race schedules.We further propose a novel algorithm to recommend an effective race schedule with minimal thread con-text switches for each data race.Our experimental results on the real applications demonstrate that 1)without removing any true data race,DFTracker effectively prunes false positives by 68%in comparison with the state-of-the-art constraint-based race detector;2)DFTracker recommends as low as 2.6-8.3(4.7 on average)thread context switches per data race in the real world,which is 81.6%fewer context switches per data race than the state-of-the-art constraint based race detec-tor.Therefore,DFTracker can be used as an effective tool to understand the data race for programmers.
基金partly supported by the National Natural Science Foundation of China(61100222)partly supported by the National Basic Research Program of China(2014CB340600)
文摘Cloud is an emerging computing paradigm.It has drawn extensive attention from both academia and industry.But its security issues have been considered as a critical obstacle in its rapid development.When data owners store their data as plaintext in cloud,they lose the security of their cloud data due to the arbitrary accessibility,specially accessed by the un-trusted cloud.In order to protect the confidentiality of data owners’cloud data,a promising idea is to encrypt data by data owners before storing them in cloud.However,the straightforward employment of the traditional encryption algorithms can not solve the problem well,since it is hard for data owners to manage their private keys,if they want to securely share their cloud data with others in a fine-grained manner.In this paper,we propose a fine-grained and heterogeneous proxy re-encryption(FHPRE)system to protect the confidentiality of data owners’cloud data.By applying the FH-PRE system in cloud,data owners’cloud data can be securely stored in cloud and shared in a fine-grained manner.Moreover,the heterogeneity support makes our FH-PRE system more efficient than the previous work.Additionally,it provides the secure data sharing between two heterogeneous cloud systems,which are equipped with different cryptographic primitives.
基金the National Key Research and Development Program of China under Grant No.2018YFB1003502the National Natural Science Foundation of China under Grant Nos.61825202,61832006,61628204 and 61702201.
文摘Graph is a well known data structure to represent the associated relationships in a variety of applications,e.g.,data science and machine learning.Despite a wealth of existing efforts on developing graph processing systems for improving the performance and/or energy efficiency on traditional architectures,dedicated hardware solutions,also referred to as graph processing accelerators,are essential and emerging to provide the benefits significantly beyond what those pure software solutions can offer.In this paper,we conduct a systematical survey regarding the design and implementation of graph processing accelerators.Specifically,we review the relevant techniques in three core components toward a graph processing accelerator:preprocessing,parallel graph computation,and runtime scheduling.We also examine the benchmarks and results in existing studies for evaluating a graph processing accelerator.Interestingly,we find that there is not an absolute winner for all three aspects in graph acceleration due to the diverse characteristics of graph processing and the complexity of hardware configurations.We finally present and discuss several challenges in details,and further explore the opportunities for the future research.
基金Supported jointly by the National Natural Science Foundation of China under Grants Nos. 61672251, 61732010, 61825202, and 61929103.
文摘Non-Volatile Main Memories (NVMMs) have recently emerged as a promising technology for future memory systems. Generally, NVMMs have many desirable properties such as high density, byte-addressability, non-volatility, low cost, and energy efficiency, at the expense of high write latency, high write power consumption, and limited write endurance. NVMMs have become a competitive alternative of Dynamic Random Access Memory (DRAM), and will fundamentally change the landscape of memory systems. They bring many research opportunities as well as challenges on system architectural designs, memory management in operating systems (OSes), and programming models for hybrid memory systems. In this article, we revisit the landscape of emerging NVMM technologies, and then survey the state-of-the-art studies of NVMM technologies. We classify those studies with a taxonomy according to different dimensions such as memory architectures, data persistence, performance improvement, energy saving, and wear leveling. Second, to demonstrate the best practices in building NVMM systems, we introduce our recent work of hybrid memory system designs from the dimensions of architectures, systems, and applications. At last, we present our vision of future research directions of NVMMs and shed some light on design challenges and opportunities.
文摘Data races are ubiquitous in multi-threaded ap- plications, but they are by no means easy to detect. One of the most important reasons is the complexity of thread in- terleavings. A volume of research has been devoted to the interleaving-insensitive detection. However, all the previous work focuses on the uniform detection (unknown to the char- acteristics of thread interleavings), thereby making the detec- tion defective in either reporting false positives or suffering from prohibitive overhead. To cope with the problem above, we propose an efficient, precise, and sound step-by-step res- olution based on the characteristics of thread interleavings. We first try to tease apart the categories of thread interleav- ings from the several typical sources arising from the lock synchronizations. We then conduct a brief study and find a new and complex pattern the previous work cannot detect. It is also revealed that the simple pattern with the majority of thread interleavings can be resolved by a simple processing to achieve a big profit for the previous reordering-based design. Our final experimental results demonstrate the effectiveness of our empiricism-based approach, and show that 51.0% of execution time and 52.3 % of trace size arising from the state- of-the-art reordering technique can be saved through a quick filtering of the simple pattern with a negligible (4.45%) per- formance overhead introduced on-the-fly.
基金supported by the National Natural Science Foundation of China under Grant Nos.61932004 and 62072205.
文摘Entity linking refers to linking a string in a text to corresponding entities in a knowledge base through candidate entity generation and candidate entity ranking.It is of great significance to some NLP(natural language processing)tasks,such as question answering.Unlike English entity linking,Chinese entity linking requires more consideration due to the lack of spacing and capitalization in text sequences and the ambiguity of characters and words,which is more evident in certain scenarios.In Chinese domains,such as industry,the generated candidate entities are usually composed of long strings and are heavily nested.In addition,the meanings of the words that make up industrial entities are sometimes ambiguous.Their semantic space is a subspace of the general word embedding space,and thus each entity word needs to get its exact meanings.Therefore,we propose two schemes to achieve better Chinese entity linking.First,we implement an ngram based candidate entity generation method to increase the recall rate and reduce the nesting noise.Then,we enhance the corresponding candidate entity ranking mechanism by introducing sense embedding.Considering the contradiction between the ambiguity of word vectors and the single sense of the industrial domain,we design a sense embedding model based on graph clustering,which adopts an unsupervised approach for word sense induction and learns sense representation in conjunction with context.We test the embedding quality of our approach on classical datasets and demonstrate its disambiguation ability in general scenarios.We confirm that our method can better learn candidate entities’fundamental laws in the industrial domain and achieve better performance on entity linking through experiments.
基金supported by the National Natural Science Foundation of China under Grant No.61972444。
文摘Computer vision(CV)algorithms have been extensively used for a myriad of applications nowadays.As the multimedia data are generally well-formatted and regular,it is beneficial to leverage the massive parallel processing power of the underlying platform to improve the performances of CV algorithms.Single Instruction Multiple Data(SIMD)instructions,capable of conducting the same operation on multiple data items in a single instruction,are extensively employed to improve the efficiency of CV algorithms.In this paper,we evaluate the power and effectiveness of RISC-V vector extension(RV-V)on typical CV algorithms,such as Gray Scale,Mean Filter,and Edge Detection.By our examinations,we show that compared with the baseline OpenCV implementation using scalar instructions,the equivalent implementations using the RV-V(version 0.8)can reduce the instruction count of the same CV algorithm up to 24x,when processing the same input images.Whereas,the actual performances improvement measured by the cycle counts is highly related with the specific implementation of the underlying RV-V co-processor.In our evaluation,by using the vector co-processor(with eight execution lanes)of Xuantie C906,vector-version CV algorithms averagely exhibit up to 2.98x performances speedups compared with their scalar counterparts.
基金This work was supported by the National Basic Research 973 Program of China under Grant No. 2014CB340600, the National Natural Science Foundation of China under Grant No. 61272072, and the Program for New Century Excellent Talents in University of China under Grant No. NCET-13-0241.
文摘In modern computer systems, system event logs have always been the primary source for checking system status. As computer systems become more and more complex, the interaction between software and hardware increases frequently. The components will generate enormous log information, including running reports and fault information. The sheer quantity of data is a great challenge for analysis relying on the manual method. In this paper, we implement a management and analysis system of log information, which can assist system administrators to understand the real-time status of the entire system, classify logs into different fault types, and determine the root cause of the faults. In addition, we improve the existing fault correlation analysis method based on the results of system log classification. We apply the system in a cloud computing environment for evaluation. The results show that our system can classify fault logs automatically and effectively. With the proposed system, administrators can easily detect the root cause of faults.
基金supported by the National Key Research and Development Program of China under Grant No.2018YFB1003502the National Natural Science Foundation of China under Grant Nos.62072195,61825202,61832006,and 61628204.
文摘With the rapid growth of real-world graphs,the size of which can easily exceed the on-chip(board)storage capacity of an accelerator,processing large-scale graphs on a single Field Programmable Gate Array(FPGA)becomes difficult.The multi-FPGA acceleration is of great necessity and importance.Many cloud providers(e.g.,Amazon,Microsoft,and Baidu)now expose FPGAs to users in their data centers,providing opportunities to accelerate large-scale graph processing.In this paper,we present a communication library,called FDGLib,which can easily scale out any existing single FPGA-based graph accelerator to a distributed version in a data center,with minimal hardware engineering efforts.FDGLib provides six APIs that can be easily used and integrated into any FPGA-based graph accelerator with only a few lines of code modifications.Considering the torus-based FPGA interconnection in data centers,FDGLib also improves communication efficiency using simple yet effective torus-friendly graph partition and placement schemes.We interface FDGLib into AccuGraph,a state-of-the-art graph accelerator.Our results on a 32-node Microsoft Catapult-like data center show that the distributed AccuGraph can be 2.32x and 4.77x faster than a state-of-the-art distributed FPGA-based graph accelerator ForeGraph and a distributed CPU-based graph system Gemini,with better scalability.
基金The work was supported by the National Key Research and Development Program of China under Grant No.2018YFB1402802the National Natural Science Foundation of China under Grant Nos.61932004 and 62072205.
文摘Real-world networks,such as social networks,cryptocurrency networks,and e-commerce networks,always have occurrence time of interactions between nodes.Such networks are typically modeled as temporal graphs.Mining cohesive subgraphs from temporal graphs is practical and essential in numerous data mining applications,since mining cohesive subgraphs gets insights into the time-varying nature of temporal graphs.However,existing studies on mining cohesive subgraphs,such as Densest-Exact and k-truss,are mainly tailored for static graphs(whose edges have no temporal information).Therefore,those cohesive subgraph models cannot indicate both the temporal and the structural characteristics of subgraphs.To this end,we explore the model of cohesive temporal subgraphs by incorporating both the evolving and the structural characteristics of temporal subgraphs.Unfortunately,the volume of time intervals in a temporal network is quadratic.As a result,the time complexity of mining temporal cohesive subgraphs is high.To efficiently address the problem,we first mine the temporal density distribution of temporal graphs.Guided by the distribution,we can safely prune many unqualified time intervals with the linear time cost.Then,the remaining time intervals where cohesive temporal subgraphs fall in are examined using the greedy search.The results of the experiments on nine real-world temporal graphs indicate that our model outperforms state-of-the-art solutions in efficiency and quality.Specifically,our model only takes less than two minutes on a million-vertex DBLP and has the highest overall average ranking in EDB and TC metrics.
基金This paper is supported by the National Natural Science Foundation of China under Grant Nos.61832006,61825202,62072193,and 61929103.
文摘Many systems have been built to employ the delta-based iterative execution model to support iterative algorithms on distributed platforms by exploiting the sparse computational dependencies between data items of these iterative algorithms in a synchronous or asynchronous approach. However, for large-scale iterative algorithms, existing synchronous solutions suffer from slow convergence speed and load imbalance, because of the strict barrier between iterations;while existing asynchronous approaches induce excessive redundant communication and computation cost as a result of being barrier-free. In view of the performance trade-off between these two approaches, this paper designs an efficient execution manager, called Aiter-R, which can be integrated into existing delta-based iterative processing systems to efficiently support the execution of delta-based iterative algorithms, by using our proposed group-based iterative execution approach. It can efficiently and correctly explore the middle ground of the two extremes. A heuristic scheduling algorithm is further proposed to allow an iterative algorithm to adaptively choose its trade-off point so as to achieve the maximum efficiency. Experimental results show that Aiter-R strikes a good balance between the synchronous and asynchronous policies and outperforms state-of-the-art solutions. It reduces the execution time by up to 54.1% and 84.6% in comparison with existing asynchronous and the synchronous models, respectively.
基金supported by the National Key Research and Development Program of China under Grant No.2023YFB4502300.
文摘Graph processing has been widely used in many scenarios,from scientific computing to artificial intelligence.Graph processing exhibits irregular computational parallelism and random memory accesses,unlike traditional workloads.Therefore,running graph processing workloads on conventional architectures(e.g.,CPUs and GPUs)often shows a significantly low compute-memory ratio with few performance benefits,which can be,in many cases,even slower than a specialized single-thread graph algorithm.While domain-specific hardware designs are essential for graph processing,it is still challenging to transform the hardware capability to performance boost without coupled software codesigns.This article presents a graph processing ecosystem from hardware to software.We start by introducing a series of hardware accelerators as the foundation of this ecosystem.Subsequently,the codesigned parallel graph systems and their distributed techniques are presented to support graph applications.Finally,we introduce our efforts on novel graph applications and hardware architectures.Extensive results show that various graph applications can be efficiently accelerated in this graph processing ecosystem.