Hyunju Lee

Taehyun Kim

Dongkyoo Shin
email: dshin@sejong.ac.kr

Heewon Park

Soohan Kim

Dongil Shin

Research on a Smart Input Device using Multimodal Biosignal Interface

This paper presents a smart input device based on multimodal analysis methods using human bio-signals. The core of the smart input device is software modules, which consist of an intelligent driving function and an analysis processing function for bio-signals. The smart input device utilizes a multimodal interface that analyzes and recognizes human bio-signal patterns. The multimodal analysis system can recognize a user's emotional and stress status by analyzing an electrocardiogram (ECG), and it can determine the user's level of concentration from electroencephalogram (EEG) patterns. To analyze the concentration, stress, and emotional status of the user, the EEG rendering system and ECG analysis system use five signal values, i.e., MID_BETA, THETA, ALPHA, DELTA, GAMMA, and the P, Q, R, S and T waves. A reformation of SVM and a clustering algorithm were applied to the user's EEG and ECG signal patterns for body context recognition. In our experiment, the on/ off status of the user's stress status controls the difficulties of the game, such as the selecting the type of race course or the number of obstacles. In addition, the speed of the car can be controlled depending on the concentration or non-concentration status of the user. The stress status of the user was predicted with an accuracy of 83.2% by the K-means algorithm, and the concentration status was predicted with an accuracy of 71.85% by the SVM algorithm. We showed that a bio-signal interface is quite useful and feasible for new games.

Introduction

Today, even though computer science and technology in the 21 st century are developing very rapidly, humans still know themselves only to a very limited extent. Most of all, advances in human computer interaction and virtual reality techniques are very important. Computing environments are moving to the human body or to human residence space from computer space in hardware development. Until intelligence inundates "to create intelligence how" the problem which is than "to deliver how" to be important, this becomes conclusion with problem of interface. Currently, it is entering the stage in which the progress of technique surpasses users' requirements, so the interface will become an efficient means for reducing the gap between the product and the user. Renovation of the interface will become an efficient means of making a priority of the effect over performance upgrade. The multimodal biology interface uses analyzed ECG and EEG signal results. Making the multimodal biology interface technique more natural and effective is the focus of the field of virtual reality, which has been developed with techniques associated with the visual/ auditory sense centers. Biofeedback games use various sensor links in the body, and the user's electroencephalogram/ electrocardiogram/ electromyograms signals are reflected in real time. Preschoolers and disabled people, for example, find existing edutainment contents difficult to use (e.g., by keyboard, mouse). The multimodal biology interface is based on this new concept, so production paradigms of the new contents are needed. This paper presents a smart input device that consists of a multimodal signal processing interface. For this study, equipment was used to measure the user's EEG and ECG signals, which are used to determine the condition of the driver. A smart device is used to ensure safe driving and to prevent risks to the driver. Users can know location using normalized values between 0 to 100. At the same time, an ECG is used to determine the emotional state and stress of the user while the user is concentrating on driving. Acquiring such biological information is applicable to the existing embodied system based on Bayesian theory. This device is suitable for driving whether or not there is a follow-up operation based on the user's location. During the process, a safe angle of rotation and safe vehicle speeds are cleverly controlled. So, the input device environment that is provided is able to cope with any emergency situations that the user may encounter. A similar situation occurred in the present experiment compared with the previous simulation environment. So, the intelligent module distinguishes the event once or repeats it by checking section status and using stored data. The intelligent module determines whether the event is temporary or ongoing. Finally, the intelligent module warns of a rapid change in risk in a specific section based on degree of similarity value.

In chapter 3 explains the composition of multimodal biology interface. Section 4 presents the results of an experimental evaluation of clustering accuracy using the reformed k-means based on EM algorithm to compare human emotion recognition performance.

Previous Work

The complexity context of the human body's signals to interactively recognize emotions relies on the detection of a physiological change attributable to an affective stimulus, followed by adequate classification of the change. Previously, most of the methods used to classify emotions using physiological signals have been based on off-line analysis of statistical features extracted from large quantities of data [START_REF] Picard | Toward Machine Emotional Intelligence/ Analysis of Affective Physiological State[END_REF]. Systems to dynamically detect, classify, and utilize emotions, based on instantaneous responses from the input device, are still lacking. Using a combination of auto associative neural networks (AANNs) and sequential analysis, a novel mechanism was developed to detect changes in physiological signals associated with emotional states [START_REF] Kramer | Auto associative Neural Networks[END_REF]. Brain Computer Interface (BCI) technology represents a rapidly growing field of research, with applications ranging from prosthetics and control systems to medical diagnostics. In this research, the experiment considers only BCI technologies that use sensors that measure and interpret brain activity (commonly referred to as neural bio-recorders [START_REF] Poli | Evolutionary brain computer interfaces[END_REF]) as a source of input. The oldest established method of neural bio-recording, which was developed in 1927 by Berger [START_REF] Haynes | Decoding mental states from brain activity in humans[END_REF], is the application of electrodes that survey the changes in field potential over time arising from synaptic currents. "In 2003, taxonomy by Mason and Birch identified MEG, PET, and fMRI as unsuitable for BCI applications, due to the equipment required to perform and analyze the scan in real time, but more recent attempts to use fMRI as a BCI input device have demonstrated significant future potential in this area [START_REF] Vaughan | Brain-computer interface technology: a review of the second international meeting[END_REF]." Brain-computer interfaces have become a topic of research interest, both as a means for obtaining user input and for studying responses to stimuli.

In our research, we controlled the speed of the car by concentration value of brain signals and the color of the car by emotional context at driving simulation content. Also, when the stress value was excessively high, the car files for overcome obstacles.

3

Design of Smart Input Device using Physiological Signals

Overall Architecture

Software modules were divided into two parts. The first part is the network software module with an I/O device, and the second part is the context manager software module for biometric data. The first part has two base modules, i.e., a client module and a server module. The client module consist of an EEG/ ECG network, and it has three modules, i.e., the initialize module, the connect module, and the data manager module. The data manager module takes charge of the radio communication data reception department, a data processing department, and the data transmission department. The server module consists of modules that interpolate game contents.

The contents network server module also has three parts, i.e., an initializer module to initialize the server, a client manager module that manages the EEG/ ECG data from the client module, and a module for receiving data from the client with a Command Processor that processes the received data. According to concentration values in the range of 0 -100, it transmits SPEED_UP or SPEED_DOWN commands and the value of the contents. Thus, it is possible to control the speed of the car in the game through concentration. The brain wave extraction is so advanced that it can extract an electromyogram signal from the blinking of the eyes.

Eye blinking occurs at regular intervals, and it delivers a left-turn command to contents. When the eye is winked twice, a right-turn command is delivered to contents. In addition, it recognizes emotion and the changes in emotion that results from the color of the car, i.e., a happy state was associated with a red car, and a sad or fearful state was associated with a blue car. Table 1 provides a definition of the interlock protocol for the physiological signal I/O device between software modules and contents. This emotion feedback technique is useful in additional contents, e.g., games and simulations. For instance, if the users are hiding from an enemy, the enemy can locate them when their emotions (stress, fear) are heightened. Thus, it is important for the mind to be calm. Table 2 shows the protocol for the ECG sensor device, which communicates with the sensor recognition utility. The sensor recognition utility transmits one byte value (0ⅹ08 and 0ⅹ09) to the electrocardiogram sensor to acquire the user's temperature and pulse. Fig . 2 shows the structure of the context manager for various signals (e.g., biology). The context manager processes context in two steps to analyse the pattern of the various acquired from the sensor devices. First, the context extractor normalizes the seven contexts between 0.1 and 0.9; all normalized contexts are used as input values to the predictor. Second, the context manager stores all contexts in the database for creation of association rules. The EEG rendering program has the following steps:

1) Input EEG data from EEG acquisition device 2) Perform pre-processing such as noise reduction and FFT analysis 3) Computation result of EEG analysis by SVM and K-means algorithm 4) Perform logistic regression for difficulty level increase/ decrease expression then two kinds of indicators, one or more values exceed certain limits of concentration status 5) Output difficulty level by user's feeling We used a non-parametic method for quantitative assessment of the EEG. Fast Fourier transformation can be used to convert the time-domain function to a frequency-domain function. 6 shows the overview screen of the contents applied in the multimodal biology interface. The direction of the input device was decided by an eye blink (EMG signal) of the user, and the input device moves according to the state of intensity of the EEG. Further, when the user feels plentiful concentration or is stressed, the input device slows down or overcomes obstacles with its flying skill, embodied with the artificial intelligence model.

Performance Results

The EM-based, K-means algorithm, which is applied in this experiment and see reformation, uses unsupervised learning with supervised learning algorithms. To verify the performance of the Human Emotion Analyzer, we used a protein data set as the input value of the human emotion analyzer. The Human Emotion Analyzer acquires electrocardiogram data (P, Q, R, S, and T waves) from the electrocardiogram sensor device and applies the peak of all waves and the RRV (r-r interval) as input values. As shown in Fig. 7, all distributions were normal. In our experiment, only the R-R interval and the R peak showed small differences in emotion and stress changes.

The neural emotion showed the highest accuracy, with the range of the three emotions at approximately 56 to 75%. Stress recognition showed a high performance result of 83%. Table 3 shows the accuracy of the performance results based on our analysis. Fig. 8 show experimental data of the non-concentration and concentration states from brain waves, respectively. The EEG rendering system extracts the brain wave feature set using the FFT algorithm. Before we decrease error factor by trend removal technique.

The concentration formula is as follows:

Concentration Indicators = Power Ratio of (SMR + M -Beta) / Theta

Theta rhythm decreases in the concentration state, and the SMR and Mid-beta rhythms indicate increases in unfocused and focused attention, respectively. Therefore, focus indicators can be quantified by the ratio of (SMR + M -beta rhythm) to Theta rhythm. Also, we convert absolute power to relative power of the FFT value for sophisticated results. The EEG rendering program calculates the concentration distinction value using SVM and the K-NN algorithm. The SVM in these experiments used the set of parameters that resulted in the highest correct rate of classification among all SVMs tested. SVMs were tested with RBF kernels with σ = 0.5. The SVMs were trained and tested using Platt's sequential minimal optimization (SMO) algorithms [START_REF] Platt | Fast training of support vector machines using sequential minimal optimization[END_REF][START_REF] Platt | Using analytic QP and sparseness to speed training of support vector machines[END_REF][START_REF] Platt | Large margin DAG's for multiclass classification[END_REF].

Conclusion and Future Work

In this paper, we have reported efforts to produce architecture for building intelligent content effects that have more efficiency than the requirement of a user's status recognition and an expedient environment. This paper describes an intelligence and complexity context analysis system using ECG and EEG patterns. The Human Emotion Analyzer evaluates differences in emotion or stress levels. We also demonstrated a sensor device that acquires continuous brainwave signals from the frontal lobe.

In this experiment, we developed a technique that analyzes the multimodal physiological signal for contents. In this paper, we proposed a method for supplying optimized information within a car and provided analysis of human body biometric signals in a driving environment to allow a user to become easily live in comport to driving in the contents. Also, physical value examined theory to achieve basic physics feedback anything. Technology than can analyzes brain waves and recognize the status of the human body is very important and can provide a foundation for research in the future. The analysis method and the intelligent system presented in this paper can be used in a wide range of diverse fields of study in future research work.

3 . 1

 31 Acquisition Devices of Physiological Signals We developed two different devices to measure EEG and ECG signals. The device on the right upside of Fig. 1 acquires brainwave signals from the frontal lobe of the brain. The four sensors must be attached to the forehead positions of the human brain. The EEG device has four channels with electrode disposition. To acquire the users' ECG signals, we also developed the ECG sensor device. The device on the left upside of Fig. 1 was used to measures the user's ECG signals. Both devices send the detected signals to a computer by Bluetooth.

Fig. 1 .

 1 Fig. 1. The External of EEG(right) and ECG(left) sensor device

Fig. 2 .

 2 Fig. 2. Structure of Context Manager

Fig. 3 .

 3 Fig. 3. EEG rendering program

Fig. 4 .

 4 Fig. 4. System architecture for mining the EEG feature Fig. 5 shows how the ECG signals are acquired and analyzed. This program assesses and displays the user's current state of emotion or stress.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Human Emotion Analyzer

Fig. 7 .

 7 Fig. 7. Distribution of RRV and R peak of stress/ non stress and three emotions states

Fig. 8 .

 8 Fig. 8. Brain wave data of non-concentration state (left) and concentration state (right)

Table 1 .

 1 Interlock protocol list of the device

	Command	To	From Client	Comment
		Server	ACK	Value
	SPEED_UP	0ⅹ02	0ⅹ02	0∼100	Concentration Value
	SPEED_DOWN	0ⅹ03	0ⅹ03	0∼100
	LEFT	0ⅹ04	0ⅹ04		Blink one time
	RIGHT	0ⅹ05	0ⅹ05		Blink two times
	FLY ON	0ⅹ06	0ⅹ06	0∼100	Stress and Non Stress State
	FLY DOWN	0ⅹ07	0ⅹ07	0∼100
	HAPPY	0ⅹ09	0ⅹ09	0∼100	Analyze Emotion as 2 Part
	SAD	0ⅹ10	0ⅹ10	0∼100	(Happy, Sad)

Table 2 .

 2 Command list of the ECG device

	Command	To		From Sensor	Command
		Sensor	ACK	#1	#2	#3
	Sensor on	0ⅹ03	0ⅹ30			Power On
	Sensor off	0ⅹ04	0ⅹ40			Power Off
	Normal Mode 0ⅹ05	0ⅹ50			Set up Normal Mode
	Stream Mode	0ⅹ06	0ⅹ6F	#D1 #D2 …	Set up Stream Mode
	Battery Status 0ⅹ07	0ⅹ71	#B		Battery(MIN)0ⅹ00∼0ⅹff(MAX)

Table 3 .

 3 Result of emotion / stress recognition

	Emotion	Correctly Classified	Incorrectly Classified	Accuracy (%)
		Instances	Instances
	Algorithm	SVM	K-means	SVM	K-means	SVM	K-means
	Fear	503	662	683	524	42.4	55.8
	Neural	737	891	449	295	62.1	75.1
	Joy	637	801	549	385	53.7	67.5
	Stress(yes)	1058	1247	440	251	70.6	83.2
	Stress(no)	1058	1247	440	251	70.6	83.2

Table 4 .

 4 Result of concentration recognition

	Classifier	Concentration State	Non-Concentration State	Average
				Accuracy (%)
	SVM	71.5	72.2	71.85
	k-NN	67.5	71.3	69.40

Acknowledgments.

This research is supported by Ministry of Culture, Sports and Tourism(MCST) and Korea Creative Content Agency(KOCCA) in the Culture Technology(CT) Research & Development Program 2009. Corresponding Author is DongIl Shin.


Zeeshan Hameed Mir
email: zhmir@etri.re.kr

Hyeon Park
email: hpark@etri.re.kr

Young Bag Moon
email: moonyb@etri.re.kr

Nae Soo Kim
email: nskim@etri.re.kr

Cheol Sig Pyo
email: cspyo@etri.re.kr

Design and Deployment of Testbed for Experimental Sensor Network Research

Keywords: Wireless Sensor Network, Experimental Testbed, Heterogeneous. In-door Testbed Users PoE Switch Testbed Server Backplane Network PoE Switch

This paper presents the Ubiquitous Sensor Network (USN) testbed, which is deployed at Electronics and Telecommunications Research Institute (ETRI), in Republic of Korea. USN testbed is a state-of-the-art sensor network experimental facility composed of various components. It includes heterogeneous sensor nodes with variety of sensing module ranging from ultralow power to high performance hardware platforms, a scalable and reliable Ethernet based wired backplane network to program, interact with and receive/send data from/to the sensor nodes, an easily extendable application software suite which glues and drive everything in a user friendly manner, and an indoor and outdoor deployment space offering various environmental characteristics. We also included two case studies where researchers have put USN testbed into practice for experimental evaluation of algorithms and networking protocols. The case studies cover routing and clustering protocol in wireless sensor networks.

Introduction

For the last few years the importance of sensor network testbed [START_REF] Crepaldi | The Design, Deployment, and Analysis of SignetLab: A Sensor Network Testbed and Interactive Management Tool[END_REF] [2] [3] [4] [START_REF] Gluhak | A survey on facilities for experimental internet of things research[END_REF] [START_REF] Rensfelt | SENSEI-A Flexible Testbed for Heterogeneous Wireless Sensor Networks[END_REF] [7] [START_REF] Des Rosiers | SensLAB: Very Large Scale Open Wireless Sensor Network Testbed[END_REF] has been continuously on the rise. Researchers are placing a considerable emphasis on the testbed infrastructure to validate theoretical system models as well as to evaluate performances of various sensor network applications. Testbed are also necessary to design, develop, and evaluate algorithms, protocols, and hardware platforms for the sensor network. There have been number of testbeds built to answer the limitations of simulation environment. However, most of these attempts tend to integrate several individual sensor nodes into a common infrastructure to achieve either certain application specific goals or a subset of the overall design objectives.

Sensor nodes must support various sensing modalities to cater diverse requirements impose by wide range of application scenarios. Moreover, the hierarchical organization of most of the sensor network applications demands sensor nodes to be built according to different capabilities at each successive level of the hierarchy. The backplane must be a reliable and scalable infrastructure for node deployment, configuration and monitoring which is vital to any testbed. It is also necessary for the backplane network to operate without causing interference with the experiment itself. The testbed management software which glues and drive everything must be user friendly and easily extendable. Finally, the deployment space of the testbed must provide a wide range of environmental characteristics and propagation attributes in the form of both indoor and outdoor testbed.

There are two main contributions of this paper. Firstly, we describe Ubiquitous Sensor Network (USN) testbed architecture and its main components. USN testbed is a state-of-the-art sensor network experimental facility which is located within the premises of Electronics and Telecommunication Research Institute, Republic of Korea. USN testbed is composed of heterogeneous sensor nodes, an Ethernet based backplane [START_REF] Crepaldi | The Design, Deployment, and Analysis of SignetLab: A Sensor Network Testbed and Interactive Management Tool[END_REF] for experiment data collection and system monitoring, a versatile application software suite that allows users to interact with the testbed in an intuitive manner. The USN testbed deployment space not only covers indoor and outdoor environments but it can easily be extended for table-top/bench-top experiments as well. The second contribution is to discuss two case studies, where researchers have put USN testbed into practice for the implementation and testing of sensor network protocols. To demonstrate the different functionalities of the testbed we shared our experiences on routing, and clustering protocols in wireless sensor networks.

The remainder of the paper is organized as follows. In Section 2, we describe the overall architecture and main components of the USN testbed. In Section 3, we discuss in details each of the constituent component namely the deployment space, backplane network, sensor nodes, and the application software suite. In Section 4, we present two case studies where researchers have implemented and tested various protocols and applications for wireless sensor network using the USN testbed. Finally, in Section 5 we conclude this paper.

Ubiquitous Sensor Network (USN) Testbed: An Overview

The USN testbad architecture consists of six main components, [START_REF] Crepaldi | The Design, Deployment, and Analysis of SignetLab: A Sensor Network Testbed and Interactive Management Tool[END_REF] [START_REF] Arora | Kansei: A High-Fidelity Sensing Testbed[END_REF]. The testbed server is used to manage information regarding NMC, sensor nodes, users etc. The testbed server transfers the control commands to the NMC and sends resultant feedback via Ethernet network. The testbed server is designed to support all the required functions and information transfer to the users. 5. USN testbed supports multiple users running sensor network applications. Each user configures nodes to use wireless channel orthogonal to those used by the other users of the testbed. 6. Sensor nodes support various requirements imposed by a wide array of sensor networking application scenarios.

Ubiquitous Sensor Network (USN) Testbed: Main Components

The Deployment Space

Currently, the indoor testbed infrastructure is installed at the 1 st and the 5 th floors of Building No. 12, at the Electronics and Telecommunications Research Institute (ETRI). However, in the past the indoor testbed was deployed at the Ground and 2 nd floors of Building No.7. The nodes at the outdoor testbed are located along the boundaries of soccer and baseball fields within the ETRI premises. Moreover, the architecture of USN testbed can easily be extended by deploying table-top testbed. Some of the main information is given as under.

 Number of nodes: The indoor and outdoor testbed has a provision of up to 40 and 100 nodes, respectively.

 Intra-node spacing: Indoor testbed (One Side: 3 m and another side: 3.5 m) and Outdoor testbed (10 m).  Height above the floor (8 cm)/ceiling (2.5 m): 180 degree rotation is possible for various node orientations (useful for studying antenna orientation and its effect on testbed physical environment).

The Backplane Network

USN testbed employs an Ethernet based backplane network. The use of wired connections allows following testbed functions in a non-intrusive manner without introducing additional interferences.  Gather debugging information,  Real-time performance evaluation statistics collection,  Transmit command/response to/from sensor nodes,  Node status check, ON/OFF, and parameter adjustment (like transmit power),  Remotely downloading code via Network Management Card (NMC),  Supply power to the sensor nodes. Out of total 10 PoE switches, five of those switches are allocated for nodes in the outdoor environment, while four are at 5 th floor and the last one is at 1 st floor of Building No. 12. Each of the PoE switch can have up to 24 ports thus enabling connection to 24 nodes via NMC.

The Hardware Platform

The sensor nodes follow layered architecture to support diverse requirements imposed by various types of applications. The basic sensor node is composed of different modules such as sensing, micro-controller, RF and power supply module interconnected via inter-module interfaces.

The basic sensor node sensing module captures variety of physical properties from the environment such as Passive Infrared (PIR), light, acoustic, temperature/humidity, magnetic, vibration sensors. The node uses low-power MSP430 micro-controller module for sensor data processing and to provide inter-module and other interfaces such as SPI, ADC, UART, GPIO etc. MSP430 micro-controller is equipped with MSP430F2618 [9], 16-bits processor with Flash (116kB+256kB)/RAM (8kB) memory and 8MB Serial Flash. The MSP430 module drives DC +3.7 V to +3.3 V from the power module to supply power to MSP430F2618, Serial Flash and other circuitry. The RF module is a 2.4GHz CC2420 [START_REF]Datasheet for Chipcon (TI) CC2420 2.4 GHz IEEE[END_REF] chipset enabling 10-250kbps for wireless communication. The sensor node is also equipped with SMA-connector in order to connect with a range of external antennas (both Omni-directional and Sectored-antenna). The nodes can be powered either by Power over Ethernet (PoE) connected via Network Management Card (NMC) or through batteries.

The hierarchical organization of most of the sensor networks demand sensor nodes to be built according to certain roles for example, basic, cluster-head and gateway nodes. The ultra-low power design of the basic sensor node supports lightweight medium access protocols, dynamic routing and self-organized networking. The sensor module can be enhanced further to capture audio and visual information as well. Hybrid sensor signal processing is provided with both low-power processor (e.g., MSP430F2618) and high performance digital signal processor (e.g., TMS320F28335 DSP [START_REF][END_REF]). The applications for cluster-head node are multiple target detection, classification and tracking, surveillance and cluster management. Finally, the role of a gateway node is to converge information from multiple heterogeneous sources either as the final destination or as an intermediate link towards the storage unit. For these purposes, the design of gateway incorporate features of basic and cluster-head nodes with some more that are specific to its own role. For example, it can have an XScale micro-controller, CDMA supporting 370kbps to 2Mbps data rates, USB, Ethernet, GPS and power connections. The potential target applications of the gateway node are remote communication (e.g., inter-networking with Multimedia Terminal Mobile (MTM), hybrid MAC protocols (e.g., fusing TDMA and CSMA), GPS-based localization etc. Table 1, summarizes the hardware platform description of basic, cluster-head and gateways nodes.

The Software Management Tool

The software management tool is actually an application software suite. It includes Graphical User Interfaces (GUIs) to, (1) Issue commands and views the final data and performance evaluation statistics. (2) Apply topology and communication protocol level parameter settings. (3) Download and program the sensor nodes independent of the underlying physical sensor network testbed and embedded operating system. Following are the main software management programs of the USN testbed.

Fig. 2. Snapshot of USN Testbed Manager GUI.

Server Program A user must run the server program to remotely establish a connection with the USN testbed server. Once a successful connection is established the testbed server then configures the connection setting with the sensor node. These connection settings are directed by application software like USN Testbed Manager and the Testbed Tester. After completing the connection setting with the sensor node the testbed server sends the ID Query messages to the sensor nodes. The sensor nodes reply with the (IP, ID) pairs. The testbed server then stores and manages the UDP socket number and ID pair of the sensor nodes. The applications programs uses sensor node's ID to send commands and data to the testbed server. The testbed server lookup the ID-UDP socket number table and report the command to the corresponding sensor nodes via NMC.

Testbed Manager This application software is a one stop solution for various tasks related with the experiment setup on USN testbed. The GUI is mainly composed of several tabs each offering a range of functions to its users. For example, a user can select nodes by choosing appropriate drop-down location options. The GUI node selection window allows selection/de-selection of a single node or a group of nodes with a simple drag and drop operation. Users then associate the NMC (with an IP address) to a particular node before downloading the source code binary. The source code binary is the compiled version generated separately using the IAR Compiler Software [12]. On successful or failed transmission of source code binary to the sensor node the appropriate result is displayed at the GUI of the user. Moreover, USN Testbed Manager also handles certain node management related function (like RESET). Fig. 2 illustrates the USN Testbed Manager software GUI.

Terminal Program

The main purpose of this program is to send command to the sensor nodes and receive data from them at runtime. The interface allows the user to select a node (by the IP address of its attached NMC) and enter any string either in ASCII or hexadecimal format.

Testbed Tester

The actual experiments are executed using the USN Testbed Tester application software. This tool allows its users to configure the network topology, functioning of the nodes and communication protocol parameters based on the experiment requirements. The users can control the number of iterations a particular experiment can run with modified experiment parameters (like packet interval). The Testbed Tester collects and displays real-time performance evaluation statistics (like Packet Success Rate, End-to-End Delay etc.), nodes channel condition (like RSSI, LQI etc.) and sensing information (like light, temperature etc.). A user can also configure experiment to collection traces on per node basis. At the end of the experiments, the generated traces are stored in the spreadsheet software for later data analysis. The Testbed Tester program is easily extendable for various types of communication protocols and customized output generation. Fig. 3 illustrates the USN Testbed Tester software GUI.

Ubiquitous Sensor Network (USN) Testbed: Case Studies

The USN testbed has been used to study the performance and analysis of several control protocols including clustering, routing, cross-layer communication and medium access control (MAC) protocols. The testbed infrastructure has also been successfully utilized to deploy sensor network applications such as target detection and classification, surveillance and reconnaissance, pedestrian tracking to name a few.

Case Study 1: MINT-based routing protocol

The USN testbed has been used to implement and test an enhanced version of the MINT (MINimum Transmission) [START_REF] Park | Large Data Transport for Real-Time Services in Sensor Networks[END_REF] routing protocol. The enhanced version deals with real-time and reliable transfer of large amount of data (e.g. image) over the sensor network testbed. The application scenario that this protocol caters for include surveillance and reconnaissance.

The enhancement incorporates heterogeneity-aware TCP-like fragmentation mechanism to decide on the network-wide MTU (Minimum Transport Unit) size. Secondly, an improved packet retransmission scheme is proposed that adapt itself to the permissible loss rate sufficient enough to maintain prescribed image quality. Finally, the protocol uses expected number of transmissions along with neighbor status information to find more reliable paths. Extra features were added in the software management tools to visualize various types of node information such as node's neighbor table, details about averaged delivery ratio and delay time etc. It is also extended to take into account several of the new messages format. The sole purpose of these messages is to enable communication between the protocol and the USN Testbed Tester and the terminal program.

Case Study 2: Static and dynamic clustering protocol

The USN testbed has been used to study the performance of static and dynamic clustering protocols. The static clustering algorithm designates few of the sensor nodes as the cluster-head during the network initialization process. While the dynamic clustering algorithm runs reactively as a result of certain event detection. In both cases the cluster-members will simply forward the data towards the cluster-head. The collected data is then aggregated at the cluster-head before it is sent to the sink node. NanoQ-Plus [START_REF] Park | A Nano Operating System for Wireless Sensor Networks[END_REF], an ETRI proprietary operating system for embedded devices has been used to design, develop and load the program code on to the sensor nodes. The Testbed Tester and the terminal program were modified to allow specialized visualization of the results of the clustering algorithms. The sensor nodes take on different shapes and color based on their role in the network as a result of applying the clustering algorithms. Further details on the clustering protocols and test results can be found in [START_REF] Moon | Efficient Cluster Head Election in Surveillance Reconnaissance Sensor Network[END_REF].

Conclusion

This paper describes USN testbed, a state-of-the-art sensor network experimental facility. It is composed of several types sensor nodes deployed at multiple indoor and outdoor locations. The testbed provides an extendable Ethernet based backplane network so that real-time information can be transmitted without interfering and compromising the operation of the sensor network applications and protocol being tested. The USN testbed software component allows multiple users to manage and run separate experiments simultaneously. These software tools are used to program, send/receive messages to/from nodes and to gather real-time debugging information and statistical results of the experiments. We also presented two case studies where the scientists and researchers at ETRI have used the USN testbed for validating their protocols and applications. The presented case studies show the usability and the applicability of the USN testbed infrastructure to understand, apply and improve research and development in sensor networks.

Fig. 1 .

 1 Fig. 1. Main components of the USN testbed.

Fig. 3 .

 3 Fig. 3. Snapshot of USN Testbed Tester GUI.

Table 1 .

 1 The Basic, Cluster-head and Gateway node hardware platform description.

	Feature	Basic node	Cluster-head	Gateway
	MCUs (1)	16Bit RISC/16Mhz 16Bit RISC/16Mhz	16Bit RISC/16Mhz
	MCUs (2)	-	32Bit	Xscale/13-520MHz
	Communication range 30m	100m	100m-7km
	Power supply	Battery/PoE	Battery/PoE	Battery/PoE
	Frequency/Data rate	2.45GHz/	433/915Mhz,2.4GHz/	2.45GHz/
	(RF 1)	10-250Kbps	40-250Kbps	250Kbps
	Frequency/Data rate	-	2.4GHz/	CDMA/
	(RF 2)	-	250Kbps	370Kbps-2Mbps
	Sensing module		PIR/30m	GPS
	/ Sensing range		Acoustic/50m	CDMA
	OR		Magnetometer/5m	USB
	Interfaces		Seismic/5m	Ethernet
	However, to execute more computation and resource intense tasks (like network-wide
	schedule computation) USN testbed features the cluster-head nodes. Cluster-head
	nodes include dual micro-controllers (MSP430 and PXA270) for low-power
	consumption and high performance. At the RF module end, it incorporates options
	like 433/915 MHz and 2.4 GHz frequency capable of supporting 40 to 250kps of data
	rates.

Acknowledgments

. This work was supported by the Dual Use Technology program of the DUTC, South Korea [Surveillance and Reconnaissance Sensor Network Development].


Xu Zhou

Kai Lu

Xicheng Lu

Xiaoping Wang

Baohua Fan

dMPI: Facilitating Debugging of MPI Programs via Deterministic Message Passing

This paper presents a novel deterministic MPI implementation (dMPI) to facilitate the debugging of MPI programs. Distinct from existing approaches, dMPI ensures inherent determinism without using any external support (e.g., logs), which achieves convenience and performance simultaneously. The basic idea of dMPI is to use deterministic logical time to solve message races and control asynchronous transmissions, thus we could eliminate the nondeterministic behaviors of the existing message passing mechanism. To avoid deadlocks introduced by dMPI, we also integrate dMPI with a lightweight deadlock checker to dynamically detect and solve these deadlocks. We have implemented dMPI and evaluated it using NPB benchmarks. The results show that dMPI could guarantee determinism with incurring modest overhead (8% on average).

Introduction

Parallel programs written in the Message Passing Interface (MPI) are inherently nondeterminism due to message races and asynchronous transmission of messages. Nondeterminism hampers the debugging of MPI programs and makes cyclic debugging a particularly challenging task [START_REF] De Kergommeaux | MPL: Efficient Record/Replay of nondeterministic features of message passing libraries[END_REF][START_REF] Clmen On | An implementation of race detection and deterministic replay with MPI[END_REF][START_REF] Xue | MPIWiz: Subgroup reproducible replay of MPI applications[END_REF][START_REF] Maruyama | Parallel program debugging based on data-replay[END_REF][START_REF] Kranzlmller | An integrated record&replay mechanism for nondeterministic message passing programs[END_REF]. Currently, researchers adopt the approaches of record & replay to eliminate the nondeterminism of MPI. These approaches record the nondeterministic events of messages, and deterministically replay the MPI programs according to the recorded logs. Since determinism is not an inherent character, these systems have limitations. First, these systems do not guarantee first-run determinism (default determinism), i.e., a program can be deterministic only after it is recorded. Moreover, one set of logs only make a certain execution of a program deterministic. When the inputs change, the program will undergo a different execution path, which is still nondeterministic. Second, deploying a record & replay system in the production environment is difficult, as they are constrained by maintaining logs. In some systems, the logging rate could be nearly 1 GB per minute for large-scale programs [START_REF] Xue | MPIWiz: Subgroup reproducible replay of MPI applications[END_REF], which presents a great challenge for the deployment of these systems. Third, these approaches are prone to cause large recording overhead, which may be unacceptable for some performancecritical programs. For example, the state-of-the-art hybrid record & replay system reported an average of 27% runtime overhead [START_REF] Xue | MPIWiz: Subgroup reproducible replay of MPI applications[END_REF].

The major problem of record & replay systems is they rely on external support to implement determinism instead of making determinism as a default property. To improve this weakness, we propose a novel deterministic Message Passing Interface (dMPI) that guarantees inherent determinism of MPI program without using any external support (e.g., logs). By using dMPI, programs are deterministic even at their first execution, thus any heisenbugs related to the message passing mechanism could be captured and debugged.

The basic design of dMPI is to conduct message transmissions and mappings according to a deterministic logical time. For any asynchronous transmission operation, dMPI forces the transmission of the message to be finished at a specific logical time, so that the process will always perceive the finishing of transmission at deterministic program point. For any promiscuous receiving operation, dMPI orders the incoming messages according to logical time to solve the nondeterminism of message races. The difficulty of this design is each process should see the distributed logical time consistently and timely to make a correct and efficient decision. To overcome this difficulty, we design the world clock and use the small-sized control messages to propagate clock values. As we put constraints on the actions of sending and receiving messages, it may cause deadlocks. To make a practical implementation, we design a lightweight deadlock checker to detect and solve these deadlocks. We have implemented dMPI as a compatible MPI library-programs only need to be linked to the dMPI library to gain the deterministic feature.

2

Design and Implementation

Nondeterminism of MPI

There are two major sources of nondeterminism in MPI: (1) the asynchronous operations and (2) the wildcard receiving operations [START_REF] De Kergommeaux | MPL: Efficient Record/Replay of nondeterministic features of message passing libraries[END_REF][START_REF] Clmen On | An implementation of race detection and deterministic replay with MPI[END_REF]. The calling of asynchronous operations (e.g., MPI_Isend, MPI_Irecv and MPI_Iprobe, etc.) may have nondeterministic effects on program states depending on the timing of message transmissions. The wildcard receiving operations (e.g., the calling of MPI_Recv with the wildcard parameter) may accept an arbitrary message if several messages are racing to arrive. The design of dMPI is to eliminate these nondeterministic effects while preserving performance maximally. Note that there may be other kinds of non-determinism in MPI programs (e.g., the nondeterminism of thread concurrency inside one process). As these problems could be addressed by existing approaches (e.g., deterministic scheduling [START_REF] Joseph | DMP: deterministic shared memory multiprocessing[END_REF]), they are not discussed in this paper. The basic design principle of dMPI is to use logical time to guide the sending and receiving of messages. Following this principle, we design dMPI as shown in Figure 1. We set a local logical clock in each process to time stamp every concerning event (e.g., the calling of MPI_Send). We add two mechanisms to ensure determinism: the deterministic waiting mechanism and the deterministic mapping mechanism. The deterministic waiting mechanism sets a Deterministic Transmission Point (DTP) for each asynchronous transmission operation. DTP is a fixed program point in the instruction stream of a process. The positions of DTPs are defined by logical time to ensure determinism. The deterministic waiting mechanism forces the transmission of asynchronous message to be finished exactly at its corresponding DTP (as shown in Figure 1), which hides the nondeterminism of asynchronous message transmission. The deterministic mapping mechanism dominates the message mapping of wildcard receiving operations according to logical timestamp of messages. For each wildcard receiving operation, it should only accept the earliest message (message with the smallest logical timestamp among all the unaccepted messages at now and in the future). Therefore, no matter when the message arrives, the wildcard receiving operation will always accept a determinate message (as shown in Figure 1, the wildcard receive always accepts M(2-4)). In this way, the deterministic mapping mechanism resolves the nondeterminism of message races.

Design Overview

Clock and Logical Time

Logical time is used to order messages and label DTPs in dMPI. To maintain a deterministic logical time, we propose the world clock which is a hybrid of Lamport clock [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] and vector clock [START_REF] Fidge | Partial orders for parallel debugging[END_REF]. World clock is a clock vector set in each process to monitor the time of all processes (including the local process). Each slot in the clock vector is corresponding to a process in the process network, describing the time of the process already seen by the local process. Different from vector clock [START_REF] Fidge | Partial orders for parallel debugging[END_REF], world clock only time stamp messages with a scalar value of the local time (we add an 8-bytes field to all kinds MPI packets). This design simplifies the mechanism of normal vector clock and reduces the communication overhead. In the clock vector, only the local time (the logical time of the local process) is precise, as it is driven by local events (e.g., calling of MPI operations, etc.). The times of other processes may be old values, as they are driven by external messages-when an incoming message is accepted, the timestamp piggybacked in this message will be used to refresh the corresponding clock vector slot if the timestamp is bigger.

To provide a correct and efficient support for message ordering and DTP creation, the driven of local logical time must meet two requirements: (1) local logical time must be precise enough to distinguish DTPs and messages, and (2) the speed of local logical time should reflect the physical time of the process execution well. The first requirement is achieved by interposing MPI APIs (e.g., MPI_Send, MPI_Recv, etc.). By doing so, no two MPI function calls will happen at the same logical time, thus messages and DTPs are easily distinguished by logical time.

The second requirement is achieved by compile-time instrumentation and the using of empirical statistics. At compile-time, we insert a time_tick event for each function call to increase the local logical time. The increased value of this function is derived from the function length (the predicted execution time of the function is based on instruction count). The compile-time instrumentation works well for memory-only codes, but is not suitable for system calls, as their execution time is hard to predict (e.g., the calling of Sleep(1) and Sleep(3) will differ much in execution time). To reflect the execution time well, we set an empirical studying table to describe the logical time values of special operations. For example, the calling of Sleep( 1) is corresponding to 1000 logical time unit in our empirical studying.

Deterministic Waiting

The logical time is used to setup DTPs to confine the finishing points of transmission operations. For any asynchronous transmission operation (e.g., MPI_Isend), the corresponding DTP is inserted at the program point that is K logical time units after the function call. Note that the value K should be constant so as to ensure determinism (In the example of Figure 1, K = 2). dMPI enforces that the transmission of message be finished right at its corresponding DTP. When an asynchronous request is posted, dMPI adds a DTP for that request. If the message arrives earlier, dMPI postpones the declaration of its arrival until the process reaches the DTP. Therefore, the issued testing function (e.g., MPI_Test or MPI_Probe) before the DTP could not perceive the arriving of the message. In the contrary, if a message is late, dMPI forces the process to wait at the DTP until the message arrives. Therefore, the testing function after the DTP will always detect the message. Note that the design of DTP only constrains the declaration of the finishing of message transmissions, while the underlying transmission is not affected. In this way, DTP creates a deterministic environment for the upper applications. To mitigate the performance degradation caused by DTP waiting, we also adopt a buffer-strategy to pre-receive messages that cannot be accepted at once.

Deterministic Mapping

The deterministic mapping mechanism solves the non-determinism of message race. When a message arrives, dMPI tries to map it with a posted receiving request. If the receiving request is not a wildcard receiving, normal mapping mechanism is used. Otherwise, we check if this message is the earliest by its timestamp. The earliest message is an unaccepted incoming message that has a smaller timestamp than any other unaccepted incoming messages (including the incoming messages that is on the way or have not been sent). We leverage the world clock to determine the earliest messages. The world clock records the logical time of all processes, thus dMPI simply compares the timestamp of the message with the values in the clock vector. If the timestamp is smaller than or equal to all the values in the clock vector, the message is considered to be the earliest and it is accepted directly. Otherwise, the message is not the earliest and the process must wait until the earliest message appears. Since the world clock only refreshes time values of other processes upon messages arrivals, the time values seen by the local process may be out-of-date, which may cause process being blocked for a long time. To mitigate this problem, we introduce the small-sized control messages to exchange information between MPI processes. The typical use of control message is to update clock vectors. We design an ondemand strategy to minimize communication overhead. The on-demand strategy works as follows. If the checking of the earliest message fails because of a smaller value in the clock vector, the process will send a Request (a control message used to ask for the logical time of another process) to the corresponding process to refresh its time. The process that receives the Request will schedule an Answer based on the local logical time. As the Request contains the expected logical time, the replying process only need to send the Answer when its logical time is greater than the expected value.

Dead Locks

The deterministic mechanisms in dMPI may introduce deterministic deadlocks which are caused by the extra wait-for dependencies. We propose a lightweight deadlock checker (LW-DC) to detect and solve these deadlocks. Different from existing general deadlock detectors [START_REF] Luecke | Deadlocks detection in MPI programs[END_REF], LW-DC is supposed to be a special deadlock detector for deterministic deadlocks only. LW-DC is a hybrid approach of timeout deadlock detector and dependency analysis detector. Since the wildcard receiving will accept a determinate message in dMPI, it greatly simplifies the design. The working procedure of LW-DC is as follows. Each process will start to check for deadlock when it stops for a while (100ms in our implementation). Then LW-DC will collect the wait-for dependency using control messages. Once LW-DC detects a cyclic dependency, it simply relaxes the deterministic mechanism to break the deadlock. Due to space limitation, we do not discuss LW-DC in detail in this paper.

Evaluation

Methodology

We implemented dMPI based on MPICH2 (version 1.4) [7]. Our evaluation hardware is consisted of 2 AMD servers connected with a 1GB/s switch. Each server has a 2.2GHz CPU with 4 cores, 1GB memory and a 1GB/s Ethernet card, running Fedora 12 with Linux kernel version 2.6.31.5. We used the NPB benchmarks [START_REF] Bailey | The NAS Parallel Benchmarks 2.0[END_REF] to test dMPI. Each benchmark is configured with 8 processes which are equally distributed among the two servers.

We verified the determinism of dMPI by [START_REF] De Kergommeaux | MPL: Efficient Record/Replay of nondeterministic features of message passing libraries[END_REF] examining the outputs of programs, (2) checking the return value for each testing function, and (3) checking the accepted message for each wildcard receiving. We ran each benchmark 100 times, and recorded the above information. We compared the results of different runs for each benchmark. Note that dMPI does not address the nondeterministic events caused by system calls (e.g., gettimeofday). Therefore, when comparing the normal program outputs, we ignored the time-related data.

To evaluate the performance, we setup a baseline execution (the performance of the standard MPICH2). We compared the performance of dMPI with the baseline execution. For each benchmark, we ran it 10 times to collect the mean value.

Execution Time

The performance of dMPI is shown in Figure 2. We divide the execution time of each benchmark into three parts: (1) the application time which is the execution time of normal program codes; (2) the instrument overhead, which is the execution time of the instrumented codes; (3) the determinism overhead, which is caused by the deterministic mechanisms. Overall, the average overhead of dMPI is small (below 8%). In Table 1, we provide the detailed profiling data of programs running under dMPI. As seen from this table, the impact of our deterministic message passing mechanism is trivial: For each program on average, dMPI additionally handles about 1200 DTPs (Column 2), 150 wildcard receiving operations (Colum 3), 2 or 3 deadlocks (Column 5). The introduced control messages are also trivial compared with the normal messages in size and number (Column 5-9).

Related Work

Record & replay is a typical method to eliminate the nondeterminism of MPI [START_REF] De Kergommeaux | MPL: Efficient Record/Replay of nondeterministic features of message passing libraries[END_REF][START_REF] Clmen On | An implementation of race detection and deterministic replay with MPI[END_REF][START_REF] Xue | MPIWiz: Subgroup reproducible replay of MPI applications[END_REF][START_REF] Maruyama | Parallel program debugging based on data-replay[END_REF][START_REF] Kranzlmller | An integrated record&replay mechanism for nondeterministic message passing programs[END_REF]. Some of them record the nondeterministic message order in the recording phase, and force the messages to follow the order of the recorded logs in the replay phase [START_REF] De Kergommeaux | MPL: Efficient Record/Replay of nondeterministic features of message passing libraries[END_REF]. Some others record the contents of messages instead of their orders [START_REF] Maruyama | Parallel program debugging based on data-replay[END_REF]. A hybrid method-MPIWiz [START_REF] Xue | MPIWiz: Subgroup reproducible replay of MPI applications[END_REF] record both message order and contents. Distinct from these works, we provide a solution for inherent determinism without any external supports (e.g., logs), which is efficient in performance and is convenient to deploy. Inherent determinism has been introduced in the shared-memory multi-processing field to facilitate debugging of multi-threaded programs [START_REF] Joseph | DMP: deterministic shared memory multiprocessing[END_REF][START_REF] Bocchino | Parallel programming must be deterministic by default[END_REF]. Although we share the same concept of inherent determinism with these works, our work is to address the nondeterministic problem of the message passing mechanism in the distributed environment, which is different from the problem of the shared-memory environment.

Conclusion and Future Work

This paper designs dMPI to facilitate the debugging of MPI programs. dMPI ensures inherent determinism by using logical time to control the finishing points of asynchronous transmissions and the accepted messages of wildcard receiving operations. We implemented and evaluated dMPI to demonstrate its practicality. The evaluation results show that the overhead of dMPI is practical and low (8%). In the future work, we will use buffering and speculation mechanism to further mitigate the performance impact of dMPI.

Fig. 1 .

 1 Fig. 1. The design overview of dMPI. "M(1-4)" indicates a message whose source is rank 1 and whose logical time is 4. "lt=2" indicates current logical time is 2.

Fig. 2 .

 2 Fig. 2. The execution time of dMPI compared with that of the standard MPI library.

Table 1 .

 1 The Detailed Information of Programs Running with dMPI

		dMPI profiling		Normal messages	Control messages
	benchmark DTP	wildcard deadlock count	size	count	size	count rate
						(Byte)		(byte)	(%)
	bt	2418	0	0	2436	283918712 0	0	0
	cg	1680	0	0	1683	46658367	0	0	0
	ep	0	0	0	9	780	0	0	0
	ft	0	0	0	40	201330833 0	0	0
	is	0.75	0	0	128	92358592	0	0	0
	lu	510	510	13.25	31661 122780595 789	3194	2.5
	mg	714	714	9	867	32057558	622	2490	71.7
	sp	4818	0	0	4836	493724232 0	0	0
	avg	1267.5 153	2.78	2436	283918712 176.4	710.5	29

Acknowledgment

This work is partially supported by National High-tech R&D Program of China (863 Program) under Grants 2012AA01A301, and by National Science Foundation (NSF) China 61103082, 61003075, 61170261 and 61103193.


Ning Deng

Yizhuo Wang

Weixing Ji

Feng Shi

Qi Zuo

Knowledge-based Adaptive Self-Scheduling *

Keywords: Knowledge-Based Adaptive Self-Scheduling loop scheduling, self-scheduling, multiprocessor system

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Loops are the dominant source of parallelism for many applications [START_REF] Polychronopoulos | Guided self-scheduling: a practical scheduling scheme for parallel supercomputers[END_REF]. In general, loops fall into two categories: DOALL loops and non-DOALL loops. DOALL loops, also known as parallel loops, do have not any loop-carried dependence. Hence, different iterations of a DOALL loop can be easily executed on concurrent threads. In this paper, we focus on DOALL loops to exploit loop level parallelism (LLP). The main problem encountered with LLP is on partitioning and allocating loop iterations among threads in a multiprocessor environment. Loop scheduling schemes have been extensively studied to deal with this problem. Existing loop scheduling schemes can be classified as static and dynamic. Static scheduling schemes partition loop iterations at compile time and statically assign iterations to processors. The static scheduling scheme results in a low runtime scheduling overhead but poor load balancing. Dynamic scheduling determines the division of iterations among processors at runtime. It leads to runtime overhead, but achieves dynamic load balancing.

Self-scheduling schemes are the most successful and widely used dynamic scheduling schemes. They partition loop iterations into chunks before execution. A chunk is assigned to an idle processor at each scheduling step at runtime. Thus, the time spent in determining how many iterations should be scheduled is saved. Most self-scheduling algorithms have decreasing size chunks, which is a result of the trade-off between load balancing and scheduling overhead. Some features of the loop and runtime environment affect the execution time of chunks. On one hand, different loops have different types of workload distribution. Non-uniform workload results in different execution times for same size chunks. On the other hand, processor speed and usage are important runtime features that determine the execution time of a chunk. Existing self-scheduling schemes are oblivious to these features. In this paper, we propose an adaptive self-scheduling scheme that utilizes the knowledge of the workload and the runtime environment with the aim of reducing synchronization costs, improving load balancing, and exploiting locality.

The rest of the paper is organized as follows. Section 2 reviews loop scheduling strategies and discusses related work. Section 3 presents the knowledge-based adaptive self-scheduling scheme in detail. Experimental results are presented in section 4, and the conclusion is presented in Section 5.

Background and Related Work

The simplest of all scheduling algorithms is static scheduling, which assigns an even number of loop iterations to each processor. It keeps the scheduling overhead to a minimum, but does not balance the load dynamically compared with the other schemes. The first self-scheduling scheme [START_REF] Smith | Architecture and Application of the HEP Multiprocessor Computer System[END_REF] is another extreme. It assigns one iteration to an idle processor each time. Hence, processors finish at nearly the same time and the workload is well balanced. However, the scheduling overhead maybe unacceptable because of the large number of scheduling steps. Self-scheduling with fixed size chunks [START_REF] Tang | Processor self-scheduling for multiple nested parallel loops[END_REF] is a tradeoff between these two rival techniques. It assigns a chunk, which consists of successive iterations, to an idle processor each time. This procedure reduces the number of scheduling steps needed, which therefore, reduces the scheduling overhead. Some self-scheduling schemes with decreasing chunk sizes were proposed to achieve better load balancing than fixed size chunking self-scheduling. They schedule large chunks at the beginning to ensure locality and reduce overhead, while scheduling small chunks at the end to balance the workload. In these self-scheduling schemes, guided self-scheduling (GSS, [START_REF] Polychronopoulos | Guided self-scheduling: a practical scheduling scheme for parallel supercomputers[END_REF]), factoring self-scheduling (FSS, [START_REF] Flynn-Hummel | Factoring: A method for scheduling parallel loops[END_REF]), and trapezoid self-scheduling (TSS, [START_REF] Tzen | Trapezoid self-scheduling: a practical scheduling scheme for parallel computers[END_REF]) are the most successful and widely used. The difference among them is the computation process for chunk sizes. None of the three schemes takes the characters of the loop and runtime factors into account. Our self-scheduling scheme quantifies these factors and uses them in calculating chunk sizes. Some dynamic self-scheduling schemes [START_REF] Tabirca | Feedback guided dynamic loop scheduling: convergence of the continuous case[END_REF][START_REF] Cariño | Dynamic load balancing with adaptive factoring methods in scientific applications[END_REF] adjust chunk sizes at run time or exploit processor affinity when mapping chunks to processors. Affinity scheduling proposed by Markatos et al. [START_REF] Markatos | Using processor affinity in loop scheduling on shared-memory multiprocessors[END_REF], employs per-processor work queues, which is similar with our scheme. However, the size of each work queue is not determined based on the knowledge of loop and runtime environment in affinity scheduling. Some groups [START_REF] Srivastava | Investigating the robustness of adaptive Dynamic Loop Scheduling on heterogeneous computing systems[END_REF][START_REF] Yang | Performance-based parallel loop self-scheduling using hybrid OpenMP and MPI programming on multicore SMP clusters[END_REF] have undertaken self-scheduling studies on particular architectures, considering the features of the system architecture. Our technique could be easily extended to these architectures.

Knowledge-based Adaptive Self-Scheduling

In this section, we describe the details of the knowledge-based adaptive self-scheduling scheme (KASS). The problem to be considered is the scheduling, across p processors P 1 , P 2 . . . , and P p , of N iterations on a parallel loop. KASS has two phases: Static partitioning phase: A knowledge-based approach is used to partition iterations of the parallel loop into local queues of processors, which makes the total workload, not the number of iterations, equally distributed onto processors approximately.

Dynamic scheduling phase: Based on self-scheduling rule, every local work queue is partitioned into chunks with decreasing sizes. Each processor allocates a chunk from its local queue to execute. A processor steals a chunk from another processor to execute when it finishes the execution of all the chunks in its local queue.

Static Partitioning

The execution time of each iteration can be obtained via loop profiling. Let t i denote the execution time of ith iteration. The mean execution time is μ t and the variance is σ t . Let l j and u j denote the lower and upper bounds of the local queue assigned to processor j.

Assuming that all the processors have the same capacity to execute the loop, static partitioning will only relate to the workload distribution of the loop. Thus, the bounds {( , ) | 1, 2,..., } j j l u j p  can be calculated by

j j u t i il N t p     (1)
Note that

1 1; l  1 1, j j l u    1, 2,..., 1; j p   . p u N  (2)
Parallel loop normally has regular workloads. Thus, t i could be well estimated by profiling [START_REF] Kejariwal | History-aware Self-Scheduling[END_REF]. In addition, prior knowledge about the loop only contributes to the static load balancing. The dynamic scheduling will further balance the workload in our scheme. Thus, prior information need not be accurate. For example, if the workload distribution of the loop is almost uniform, no profiling is needed, and t i (i=1, 2…, N) could just be set to any fixed number.

In addition to loop features, differences in processor speed, load running, and architecture can significantly impact performance. We use a i to represent the capacity of processor P i to execute the loop. In a simple case, let s i denote the speed of P i and b i denote how much of P i 's capacity is used in the execution of this application. Then, a i = s i b i . We normalize a i with a 1 . For instance, a 1 =1 and a 2 =2, which means that the execution time of the same workload on P 1 is twice as that on P 2 . Subsequently, the loop bounds of the local queues can be calculated using the following equations under the assumption that the loop is uniform.

1; l  1 1; j j l u    1 1 , 1, 2,..., 1; j p j i i i i u a a N j p                    . p u N  (3)
Considering the aspects of loop workload distribution and processor capacity, the bounds should be determined using 1 [START_REF] Polychronopoulos | Guided self-scheduling: a practical scheduling scheme for parallel supercomputers[END_REF] 1

j j j j u u p i i i l j i l j j t t p a a                (4)
where the discrete function of t i is approximately equally partitioned among p processors. Unfortunately, the approximation of (4) does not provide a simple computation. We propose a heuristic method to calculate the loop bounds {( , ) | 1, 2,..., } j j l u j p  . Let j l and j u denote the bounds calculated using equation (1). Let j l and j u denote the bounds calculated using equation [START_REF] Tang | Processor self-scheduling for multiple nested parallel loops[END_REF]. We initialize the bounds as follows:

1 1; l  1 1; j j l u    , 1, 2,..., 1. 2 j j j u u u j p             ; p u N  (5)
Consequently, the execution time of iterations from l j to u j on processor P j is calculated as follows:

1 , 1, 2,..., .

j j u j i il j T t j p a     (6)
The mean of T j is μ T and the variance is σ T . Our goal is to make all T j as equal as possible, i.e., all the processors finish the execution at approximately the same time. For a processor P j , if T j is greater than μ T , the processor has much workload, thus, we need to decrease the number of iterations assigned to P j that results in the adjustment of the bounds, and vice versa. The change is defined as ( ) /

T j T t

 

, where t is the mean execution time of iterations, which is defined as

1 p j j t T N   
.

The above procedure is repeated to adjust the bounds until one of the following conditions is met:

1) The maximum number of steps, which is user inputted, is reached.

2) The coefficient of variation (c.o.v.) of T j (σ T /μ T ) becomes less than a threshold value, which is set to 0.1 in our experiments.

3) The variance (σ T ) in the current step is greater than that in the last step. To summarize, we determine the loop bounds of the local queues in the static partitioning phase using the following rules:

1) If the c.o.v of the execution time of iterations (σ t /μ t ) is less than 0.1, the bounds are calculated using equation [START_REF] Tang | Processor self-scheduling for multiple nested parallel loops[END_REF]. Since the loop has nearly uniform workload distribution in this case, we just take the capacities of the processors into account.

2) If the c.o.v of the capacities of the processors (σ a /μ a ) is less than 0.1, the bounds are calculated using equation [START_REF] Polychronopoulos | Guided self-scheduling: a practical scheduling scheme for parallel supercomputers[END_REF]. The processors have almost same capacity in this case, thus, we just take the workload distribution into account.

3) In other cases, the heuristic method introduced above is used.

Dynamic Scheduling

In the dynamic scheduling phase, each local iteration queue is partitioned into chunks. A self-scheduling algorithm is then applied to assign a chunk to an idle processor in each scheduling step. A chunk size tuning parameter k i is set for processor P i (i=1,2,...,p) to balance between data locality and parallelism. Each processor always removes k i of the remaining iterations in its local queue for execution. P i turns to help other heavily loaded processors after completing the execution of the iterations in its local queue. In our implementation, P i allocates k i of the remaining iterations from the next unfinished work queue for execution. Considering synchronization cost, a chunk should not be too small. Thus, another parameter α, which is the minimal number of iterations in a chunk, is identified. The sketch of KASS is presented in Fig. 1. Next, we present the identification of tuning parameters k i and α. Previous work in [START_REF] Liu | Safe Self-Scheduling: A Parallel Loop Scheduling Scheme for Shared-Memory Multiprocessors[END_REF] shows that the chunk size should range from R/2p to R/p in a self-scheduling scheme with a central work queue to have reasonable load imbalance and synchronization overhead. R is the number of the remaining iterations. The chunk size would range from 0.5 R to R when the same principle is applied to per-processor work queues. Therefore, the range of k i should be [0.5, 1]. The selection of k i relates to two factors: the "error" of static partitioning and the dynamic changes of runtime environment. We use c.o.v (σ/μ) to represent the error of static partitioning. Three cases in static partition phase were noted, as described in section 3.1. We use σ a /μ a when σ t /μ t < 0.1; use σ t /μ t when σ a /μ a < 0.1; use σ T /μ T for other cases. The range of σ/μ is [0, 0.1]. Let Δ denote the dynamic changes in the runtime environment, which ranges from 0 to 0.4 to enforce k i ranging from 0.5 to 1. The chunk size tuning parameter k i is defined as 1 / , 1, 2,..., .

i k i p       (7)
The value of Δ is user inputted. Our experiment results suggest that it is optimal to set Δ to 0.1 when the system is relatively stable. Thus, the value of k i is 0.8.

The tuning parameter α limits the minimal size of a chunk. If the time that a processor spends to steal a chunk from another processor is longer than the execution time of this chunk, it is clear that chunk stealing need not be done. Performance penalty of work stealing in the present comes from two aspects. One is the synchronization overhead, which refers to the time cost of the critical sections in shared memory multiprocessor systems. Another is the loss of data locality, which is mainly the cache miss penalty in shared memory systems, and is considered as communication cost in distributed memory systems. The execution time of the critical section used to allocate a chunk via profiling is obtained. Let T cs denote it. The minimal number of iterations of a chunk is defined as α = 2T cs /μ t , where, μ t is the mean execution time via profiling. The above equation does not take the effect of locality into account because locality is hard to quantify. Hence, we enlarged the synchronization cost to fill up the loss.

KASS for Loop Nests

For loop nests with sequential outer loop and parallel inner loop, we improve the KASS algorithm by adaptively changing k i for each processor. A counter C i is set for processor P i . C i is increased by one each time the processor P i removes a chunk from another processor P j . Accordingly, C j is decreased by one. The counters are initially set to zero at the beginning of every step in the outer loop. At the end of the outer loop step, the processors are classified into three types based on the value of the counters:  Lightly loaded: the C i value of the processor is greater than a positive integer θ, which is a threshold set by the user. We set θ to 1 in our experiments.  Normally loaded: the C i value of the processor is within the range of [-θ, θ].  Heavily loaded: the C i value of the processor is less than -θ. If P i is a heavily loaded processor, less iterations should be assigned to it at each scheduling step so that more iterations remaining in the heavily loaded processor can be executed by the lightly loaded processors. k i is decreased to realize the adjustment. On the contrary, k i is increased for lightly loaded processors so that these processors can finish the chunks in their local work queue as soon as possible, and then start to help heavily loaded processors. The value of k i is adjusted to i k as follows: min(0.9, 0.1) if if max(0.5, 0.1) if

i i i i i i i k C k k C k C                    (8)
The KASS algorithm for loop nests is similar to the affinity scheduling proposed by Markatos et al. [START_REF] Markatos | Using processor affinity in loop scheduling on shared-memory multiprocessors[END_REF]. Both of these algorithms use per-processor work queues and utilize work-stealing to balance the workload. Three important differences between KASS and affinity scheduling exist. First, static partitioning in KASS is knowledge-based, whereas affinity scheduling makes equivalence partitioning. Second, chunk sizes are adaptively changed by the adjustment of k i in KASS. In affinity scheduling, chunk sizes are fixed during multiple execution times of the inner DOALL loop. Third, KASS limits the minimal chunk size, whereas affinity scheduling does not. Excessive partitioning as in some cases in affinity scheduling causes harmful effects on data locality and overall performance.

Experiments

In this section, we present our experimental setup and results. KASS is compared with other popular loop scheduling schemes in two cases studies: one for outer most parallel loops; another for loop nests.

For the case study on outermost loops, we extracted several kernels from SPEC CPU2000/2006 benchmarks. The detail of the kernel set is presented in Table 1. For the case study on loop nests, the selected application kernels are Successive Over-Relaxation (SOR), Jacobi Iteration (JI), and Transitive Closure (TC) [START_REF] Markatos | Using processor affinity in loop scheduling on shared-memory multiprocessors[END_REF]. The detailed experimental setup is provided in Table 2.

Study on Outermost Parallel Loops

GSS, FSS, and TSS are widely used loop scheduling schemes in practice. For each kernel in Table 1, we compare execution times obtained with static scheduling, GSS [START_REF] Polychronopoulos | Guided self-scheduling: a practical scheduling scheme for parallel supercomputers[END_REF], FSS [START_REF] Flynn-Hummel | Factoring: A method for scheduling parallel loops[END_REF], TSS [START_REF] Tzen | Trapezoid self-scheduling: a practical scheduling scheme for parallel computers[END_REF], and KASS. Experiments were run by varying the number of threads from 2 to 16. All worker threads are bound on different cores.

Several artificial loads are added to processors P 1 , P 3 , P 5 ,..., and P 15 when testing. Thus, a i = 1 (i = 1, 3, ..., 15) and a i = 2 (i = 2, 4, …, 16) in the static partition phase of KASS. L1 to L9 use equation ( 3) to calculate the bounds of local partitions. L10 has obvious non-uniform workloads. Hence, the heuristic method is applied to obtain the bounds. k i is set to 0.8 because there are no other unknown loads running in the system. The parameter α is determined via profiling for each kernel.

We report the speedups over sequential versions of the codes for each scheduling scheme in Fig. 2. The execution time of the sequential versions is the average value of the execution times in loaded and unloaded environments on one core. We observed that for all ten kernels, both KASS and the classic self-scheduling schemes (GSS, FSS, and TSS) show significant improvement over static scheduling. Although static scheduling has better data locality than other schemes of scheduling and has no synchronization cost, poor load balancing made it much worse than self-scheduling.

Figure 2 shows that KASS is the most effective self-scheduling scheme. Comparing KASS with GSS, FSS and TSS, we observe that KASS is 16.9% faster than GSS on average with 8 threads, which is the best case, and 4.8% faster than FSS on average with 16 threads, which is the worst case. Again, we notice that GSS is worse than other self-scheduling schemes on average due to the large chunk size allocated in the first scheduling step.

The performance gains obtained from KASS can be attributed to load balancing, synchronization overhead and data locality. KASS only needs synchronization during work stealing. In the ideal case, the number of locks can be as low as the number of threads if the workload was balanced perfectly in the static partition phase. For the other three self-scheduling schemes, the number of locks equals the number of chunks, and the value never changes during numerous executions times. Aside from synchronization overhead, data locality is another significant benefit of using distributed work queues. For the outmost parallel loop, spatial locality is improved because most chunks in the local queue are executed successively by the local processor. For nested loops, distributed work queues enforce processor affinity with the data set. Therefore, temporal locality is improved. To gain better insight into the performance issues, we collected L1 and L2 cache misses with Pfmon2 for each kernel and each self-scheduling scheme. Figure 3 shows the results when 4 threads are used. Cache misses are normalized against cache misses in GSS. KASS has less L1 data cache misses than others. L2 cache misses decrease slightly except for L10. The matrix size in L10 is 3200 x 3200, thus, it cannot be loaded into the L2 cache entirely. Moreover, matrix transposition has decreasing workload distribution. Therefore, L10 presents much variation in cache misses.

Study on Loop Nests

To the best of our knowledge, affinity scheduling is most similar with our technique for loop nests. We implemented KASS algorithm as presented in Section 3, and the affinity scheduling algorithm (AFS) in [START_REF] Markatos | Using processor affinity in loop scheduling on shared-memory multiprocessors[END_REF]. Three applications (SOR, JI, and TC) were run on 2 cores to 16 cores with N = 10000. The average execution times are reported in Fig. 4. KASS performs better than AFS in all cases. The speedups of KASS over AFS in the figure are also labeled. The maximal speedup is 1.27, which makes KASS 21% faster. As discussed in Section 3, the attained performance is mainly attributed to knowledge-based static partition and adaptive adjustment with tuning parameters. Both KASS and AFS exploited processor affinity with distributed work queues. Work stealing happens when load imbalance arises between initial partitions. A significant disadvantage with the AFS scheduling scheme exist where work stealing has dramatically increased scheduling overhead when more processors are used. Therefore, KASS should achieve greater speedup when more processors are used because of relatively balanced initial partition and adaptive adjustments, which result in less work stealing than AFS. This trend has been noticed in Fig. 4

Conclusion

A knowledge-based adaptive self-scheduling (KASS) algorithm for parallel loops has been proposed in this paper. An experimental study was performed to compare the KASS algorithm with classic self-scheduling algorithms (GSS, TSS, and FSS), static scheduling, and affinity scheduling algorithm. The major conclusions from the study are: Dynamic scheduling schemes perform well for all kernels. KASS performs better than classic self-scheduling and static scheduling for the outermost loops. For loop nests, KASS not only exploits processor affinity, but also adaptively adjusts chunk partitions. Therefore, KASS achieved better performance compared with affinity scheduling. Future work would be geared towards implementing KASS on heterogeneous computing systems.

1

 1

Fig. 1 .

 1 Fig. 1. The sketch of KASS

Fig. 2 .

 2 Fig. 2. Speedup over sequential execution

Fig. 3 .

 3 Fig. 3. Cache misses when 4 Threads used

  (b).

Fig. 4 .

 4 Fig. 4. Execution time of SOR (a), JI (b) and TC (c)

Table 1 .

 1 Kernel Set

	Kernel	Suite	Benchmark	File, line
	L1	SPEC2000 179.art	scanner.c, 317
	L2	SPEC2000 188.ammp	rectmm.c, 405
	L3	SPEC2000 183.equake	quake.c, 462
	L4	SPEC2006 470.lbm	lbm.c, 186
	L5	SPEC2006 433.milc	quark_stuff.c, 1523
	L6	SPEC2006 462.libquantum gates.c, 89
	L7	SPEC2006 464.h264ref	mv-search.c, 394
	L8	SPEC2006 482.sphinx3	vector.c, 512
	L9	Matrix Multiplication	mm.c
	L10	Matrix Transpose	mt.c

Table 2 .

 2 Experimental Setup

	Processor	4 X Intel ® Xeon ™ X7350 (4 cores/chip)
		@ 2.93GHz
	L1 Data Cache	32 KB
	L2 Cache	2 X 4 MB
	Memory	8 GB
	Compiler	gcc 4.2.4
	Compiler Flags	-O2 -lpthread -lrt -lm
	Thread Library	NPTL 2.7
	OS	Linux ubuntu
		2.6.22.14

* This work was supported by the National Natural Science Foundation of China (60973010).


Jintao Meng
email: jt.meng@siat.ac.cn

Jianrui Yuan
email: jr.yuan@siat.ac.cn

Jiefeng Cheng
email: jf.cheng@siat.ac.cn

Yanjie Wei
email: yj.wei@siat.ac.cn

Shengzhong Feng
email: sz.feng@siat.ac.cn

DGraph: Algorithms for shortgun reads assembly using De Bruijn Graph

Keywords: De Bruijn graph, graph algorithm, short read assembler

Massively parallel DNA sequencing platforms have become widely available, reducing the cost of DNA sequencing by over two orders of magnitude, and democratizing the field by putting the sequencing capacity of a major genome center in the hands of individual investigators. New challenges include the development of robust protocols for generating sequencing libraries, building effective new approaches to resequence and data-analysis. In this paper we demonstrate a new sequencing algorithm, named DGraph, which has two modules, one module is responsible to construct De Bruijn graph by cutting reads into k-mers, and the other's duty is to simplify this graph and collect all long contigs. The authors didn't adapt the sequence graph reductions operations proposed by RAMANA M.IDURY or Finding Eulerian Superpaths proved by Pavel A.Pevzner or bubble remove steps suggested by Danial Zerbino, As the first operations was computing expensive, and the second one was impractical, and the last one did not benefit either the quality of contigs or the efficiency of the assembler. Our assembler was focused only on efficient and effective error removal and path reduction operations. Applying DGraph to the simulation data of fruit fly Drosophila melanogaster chromosome X, DGraph (3min) is about six times faster than velvet 0.3 (19 mins), and its coverage (92.5%) is also better than velvet (78.2%) when k = 21. Compare to velvet, the results shows that the algorithm of DGraph is a faster program with high quality results.

Introduction

Each cell of a living organism contains chromosomes composed of a sequence of DNA base pairs. This sequence, the genome, represents a set of instructions that controls the replication and function of each organism. The automated DNA sequencer gave birth to genomics, the analytic and comparative study of genomes, by allowing scientists to decode entire genomes. Although genomes vary in size from millions of nucleotides in bacteria to billions of nucleotides in humans and most animals and plants, the chemical reactions researchers use to decode the DNA base pairs are accurate for only about 600 to 700 nucleotides at a time.

The process of sequencing begins by physically breaking the DNA into millions of random fragments, which are then "read" by a DNA sequencing machine. Next, a computer program called an assembler pieces together the many overlapping reads and reconstructs the original sequence. This general technique, called shotgun sequencing, was introduced by Fred Sanger in 1982. Recently, new sequencing technologies have emerged [START_REF] Michael | Gibbs: Electrophoretically Uniform Fluorescent Dyes for Automated DNA Sequencing[END_REF] (Metzker 2005), for example, pyrosequencing (454 sequencing) [START_REF] Margulies | Genome sequencing in microfabricated high-density picolitre reactors[END_REF] (Margulies et al. 2005) and sequencing by synthesis (Solexa) [START_REF] Bentley | Whole-genome re-sequencing[END_REF] (Bentley 2006), both commercially available. Compared to traditional Sanger methods, these technologies produce shorter reads, currently ~200 bp for pyrosequencing and 35bp for Solexa. Until recently, very short read information was only used in the context of a know reference assembly, either for sequencing individuals of the same species as the reference, or readout assays.

Sequencing remains at the core of genomics. Current sequencing approaches are classed into two strategies. The first one is overlap-layout-consensus, its applications includes TIGR assembler [START_REF] Granger | TIGR Assembler: A New Tool for Assembling Large Shotgun Sequencing Projects[END_REF], Phrap [5], and CAP3 [START_REF] Huang | CAP3: A DNA Sequence Assembly Program[END_REF]; the second one is graphtheoretical approach, and its applications includes VCAKE [START_REF] Kreuze | Complete viral genome sequence and discovery of novel viruses by deep sequencing of small RNAs: A generic method for diagnosis, discovery and sequencing of viruses[END_REF], SSAKE [START_REF] René | Assembling millions of short DNA sequences using SSAKE[END_REF], Velvet [START_REF] Zerbino | Velvet: algorithms for de novo short read assembly using De Bruijn graphs[END_REF].

The assembler following the first approach must first build the graph by computing all possible alignments between the reads. A second stage cleans up the graph by removing transitive edges and resolving ambiguities. The output of this stage comprised a set of nonintersecting simple paths in this refined graph, each such path corresponding to a contig. A final step generates a consensus sequence for each contig by constructing the multiple alignments of the reads that is consistent with the chosen path. Although this approach are relatively easy to implement, but they are inherently local in nature and ignore long-range relationships between reads, which could be useful in detecting and resolving repeats. In addition, all current implementations of the greedy method require huge memory. This limits their applicability on current available hardware to organisms with gnomes of 32 Mbp or less.

The second approach to shotgun sequence assembly uses a sequencing-byhybridization technology. The idea is create a virtual SBH problem by breaking the reads into overlapping n-mers, where an k-mer is a substring of length k from the original sequence. Next, the assembler builds a directed De Bruijn graph in which each edge corresponds to an k-mer from one of the original sequence reads. Finally, the problem of reconstructing the original DNA molecule corresponds to finding a path that uses all the edges-that is, an Eulerian path. In theory, the Eulerian path approach is computationally far more efficient than the overlap-layout-consensus approach because the assembler can find Eulerian paths in linear time while the problems associated with the overlap-layout-consensus paradigm are NP-complete. Despite this dramatic theoretical difference, the actual performance of existing algorithms indicates that overlap-layout-consensus approach is just as fast as the SBH-based approach.

The algorithm proposed in this paper fell into the graph-theoretical approach. As computation time and quality of contigs still limit the practical use of these implementations adopting de Bruijn graphs approach to genomes on the order of a billion base in size. Compared with the previous works, DGraph will pay attention to these two points. For this result, the authors didn't adapt the sequence graph reductions operations proposed by RAMANA M.IDURY or Finding Eulerian Superpaths proved by Pavel A.Pevzner or bubble remove steps suggested by Danial Zerbino, As the first operations was computing expensive, and the second one was impractical, and the last one did not benefit either the quality of contigs or the computation efficiency of the assembler. Our assembler was focused only on efficient and effective error removal and path reduction operations.

We organize the paper as follows, Section II will introduce the operations of two modules in detail. The experiment and performance will be demonstrated in Section III, and the last section will discuss the weak points of the algorithm and our further work.

Algorithmic Approach

The processes of the algorithm DGraph was descript in figure 1. DGraph has two modules, the first one is graph construction, which is responsible to construct De Bruijn graph by cutting reads into k-mers, and the second one is graph simplification whose duty is to simplify this graph.

Graph Construction Module

In the De Bruijn graph, each node represents a k-mers, and adjacent k-mers overlap each other with k-1 nucleotides. Each node N is attached to the node ~N, which represents the reverse series of reverse complement k-mers. The adjacent nodes are connected by arc, for each node A to B, a symmetric arc goes from ~B to ~A.

For each read, we cut it into k-mer (k must be an odd number, k<32) and keep it into a hash table. For each k-mers, the hash table will keep this string of k-mers and its node ID in the graph. Each k-mer has a reverse complement.

Then, all adjacent k-mers (or nodes) in the same read are connected. Its reverse complement is also linked with a reverse arc. Each arc has a weight to record how many reads contain this two k-mers. The Construction module of DGraph processes each reads and connects all adjacent k-mers to build a De Bruijn graph.

Graph Simplification Module

Error link removal

Generally speaking, 1%~3% errors will be imported into De Bruijn graph from input reads because of the precision of modern sequencing machines. All low coverage arcs will be thought as error links and must be deleted.

There will be a threshold θ for each arc in the De Bruijn graph, if the weight of arc is less thanθ, this arc will be deleted. Then if some node is disconnected with other nodes we will also delete that node.

Path Simplification

This step is to simplify the De Bruijn graph. When a node A has only one outgoing arc that points to node B, then the two nodes can be merged, and their reverse complements should be merged too.

Our module will degrade each chain of nodes into one node. After simplification, the number of nodes will be greatly declined. There possibly are some isolated nodes, we simply delete all of these isolated nodes, as we think it was introduced by error reads.

Tips Removal

Tip is a chain of node which disconnected on one end. All tips will be removed if it is shorter than 2k, this parameter is a cutoff length which was chosen to delete all erroneous constructs. After that our algorithm produced a much more simply graph without loss of information. We did not do any further operations as the other algorithm does, because we did not agree that bubbles removing step was appropriate operation in velvet [START_REF] Zerbino | Velvet: algorithms for de novo short read assembly using De Bruijn graphs[END_REF], it simply combined two path from node A to node B into one, but these two path may actually exist in the finally contigs. We also did not apply graph reduction operation mentioned in [START_REF] Rm Idury | A New Algorithm for DNA Sequence Assembly[END_REF], in principle, this algorithm was great, it did give a way to simplify the De Bruijn graph; However it is not practical to realize the graph reduction, and the complexity on maintain the data structure defined in [START_REF] Rm Idury | A New Algorithm for DNA Sequence Assembly[END_REF] is enormous high, not to mention their complex mathematic operation. Even the prototype developed by the authors of [START_REF] René | Assembling millions of short DNA sequences using SSAKE[END_REF] will use 10s on assembling 20k data.

Experimental Results

The sequence data is produced from Drosophila melanogaster (fruit fly) chromosome X (its sequence size is 21.7M, the NCBI reference sequence ID is NC_004354.3). Our reads producer program will cut NC_004354.3 into short reads with length range from 200bp to 400bp, and the coverage of our read set is 30. Errors rate of 1% was introduced into the read set. The final size of the read set is about 571M.

The DGraph algorithm was compared with velvet 0.3 in our Evaluation in both contig quality and algorithm performance.

The read set will be assembled by DGraph and velvet. We ran the entire test with different parameter k, which was an odd number ranged from 19 to 31. We verified the assemblies by aligning the resulting contigs to the reference sequence by NCBI blast [11] to calculate the quality of the results.

First, the quality analysis of the resulting contigs was illustrated from figure 2 to figure 7. Figure 2 shows that the number of resulting contigs produced by DGraph are about two-third as many as the number of contigs output by velvet. In max length of contigs, DGraph is two times longer than velvet according to figure 3. The same trend also happens in figure 4 on their N50 length. Figure 5 demonstrated that DGraph has less number of contigs larger than N50 compared to velvet, which means that contigs produced by DGraph are mainly consisted with a few long contigs and a large amount of short contigs. All in all, the four figure shows that DGraph has much less but much longer contigs longer than N50 compared with velvet. What's more, the coverage of DGraph's resulting contigs (92.5%) is slightly better than the coverage of velvet's according (78.2%) to figure 6.

Second, In figure 7, DGraph consumed about one-sixth as much cpu time as velvet did, which is 3minutes and 19minutes respectively. But in terms of memory consumption DGraph is two times larger than velvet. Generally speaking, DGraph can produce higher quality of resulting contigs with one-sixth cpu time used by velvet, only at the cost of more memory.

Discussion

The DNA sequencing technology field has become a quickly moving target, Fast and high quality Algorithms that can assemble millions of small DNA fragments into gene sequences are located in our research scope. DGraph, a new de novo sequencing algorithm was proposed in this paper, Core operations, such as graph construction and graph simplification was implemented effectively to support high quality configs. The experiment demonstrated that DGraph outperformance velvet both on assembler speed and contigs' quality. DGraph was just a basical assembler framework on resequencing, father optimization on memory consumption and code parallelization was urgent work in the development of next version. Last, but not least, is there exist a practical method to reduce the simplified graph, Can this method work efficiently and indeed improve the quality of resulted contigs.

Fig 1 .

 1 Fig 1. The processes of algorithm DGraph.

Fig. 2 Fig. 3

 23 Fig.2 Number of contigs with length larger than 100bp

Fig. 5 Fig. 6 Fig. 7

 567 Fig.5 Number of contigs with length longer N50

Acknowledgements

This work is supported by NSFC (Grant No. 61103049) and Shenzhen Research Fund (Grant No.JC201005270342A). The author also thanks Lin Fang, Bingqiang Wang and their teammates from BGI, and Sitong Sheng from HYK Gene for their supports and suggestions on this work.