page 13.1. ACMV Method of statement - Ventilation System

ACM评判结果.txt如果你同时爱几个人，说明你年轻；如果你只爱一个人，那么，你已经老了；如果你谁也不爱，你已获得重生。

积极的人一定有一个坚持的习惯。

本系统可以对您提交的源代码进行编译并且运行，然后判断您提交的程序是否符合题目的要求，最后给出相应的信息。

具体信息如下：Waiting :系统无法在第一时间给所有提交以评判结果。

Compiling : 您提交的代码正在被编译。

Running : 您的程序正在系统上运行。

Accepted (AC) : 您的程序是正确的，恭喜！Presentation Error (PE) : 虽然您的程序貌似输出了正确的结果，但是这个结果的格式有点问题。

请检查程序的输出是否多了或者少了空格（' '）、制表符（'\t'）或者换行符（'\n'）。

Wrong Answer (WA) : 输出结果错，这个一般认为是算法有问题。

Time Limit Exceeded (TLE) : 您的程序运行的时间已经超出了这个题目的时间限制。

Memory Limit Exceeded (MLE) : 您的程序运行的内存已经超出了这个题目的内存限制。

Output Limit Exceeded (OLE) : 您的程序输出内容太多，超过了这个题目的输出限制，多半是死循环引起的。

Compilation Error (CE) : 您的程序语法有问题，编译器无法编译。

具体的出错信息可以点击链接察看。

Out Of Contest TIme : 比赛已经结束，这个只有在比赛中才会出现Runtime Error (RE) : 运行时错误，这个一般是程序在运行期间执行了非法的操作造成的。

以下列出常见的错误类型：ACCESS_VIOLATION 您的程序想从一些非法的地址空间读取或向其中写入内容。

一般例如指针、数组下标越界都会造成这个错误的。

INTEGER_DIVIDE_BY_ZERO 在进行整数除法的时候出现了除数为零的异常。

Your Paper's Title Starts Here: Please Centeruse Helvetica (Arial) 14First Author1, a, Second Author2,b and Others3,c1Full address of first author, including country2Full address of second author, including country3List all distinct addresses in the same waya email,b email,c emailKeywords:List the keywords covered in your paper. These keywords will also be used by the publisher to produce a keyword index.For the rest of the paper, please use Times Roman (Times New Roman) 12Abstract. This document explains and demonstrates how to prepare your camera-ready manuscript for Trans Tech Publications. The best is to read these instructions and follow the outline of this text. The text area for your manuscript must be 17 cm wide and 25 cm high (6.7 and 9.8 inches, resp.). Do not place any text outside this area. Use good quality, white paper of approximately 21 x 29 cm or 8 x 11 inches (please do not change the document setting from A4 to letter). Your manuscript will be reduced by approximately 20% by the publisher. Please keep this in mind when designing your figures and tables etc.IntroductionAll manuscripts must be in English. Please keep a second copy of your manuscript in your office (just in case anything gets lost in the mail). When receiving the manuscript, we assume that the corresponding authors grant us the copyright to use the manuscript for the book or journal in question. Should authors use tables or figures from other Publications, they must ask the corresponding publishers to grant them the right to publish this material in their paper.Use italic for emphasizing a word or phrase. Do not use boldface typing or capital letters except for section headings (cf. remarks on section headings, below). Use a laser printer, not a matrix dot printer. Organization of the TextSection Headings. The section headings are in boldface capital and lowercase letters. Second level headings are typed as part of the succeeding paragraph (like the subsection heading of this paragraph).Page Numbers. Do not print page numbers: Please number each sheet toward the middle near the bottom (outside the typing area) with a soft pencil.Tables. Tables (refer with: Table 1, Table 2, ...) should be presented as part of the text, but in such a way as to avoid confusion with the text. A descriptive title should be placed above each table. The caption should be self-contained and placed below or beside the table. Units in tables should be given in square brackets [meV]. If square brackets are not available, use curly {meV} or standard brackets (meV).Figures. Figures (refer with: Fig. 1, Fig. 2, ...) also should be presented as part of the text, leaving enough space so that the caption will not be confused with the text. The caption should be self-contained and placed below or beside the figure. Generally, only original drawings or photographic reproductions are acceptable. Only very good photocopies are acceptable. Utmost care must be taken to insert the figures in correct alignment with the text. Half-tone pictures should be in the form of glossy prints. If possible, please include your figures as graphic images in the electronic version. For best quality the pictures should have a resolution of 300 dpi(dots per inchEquations. Equations (refer with: Eq. 1, Eq. 2, ...) should be indented 5 mm (0.2"). There should be one line of space above the equation and one line of space below it before the text continues. The equations have to be numbered sequentially, and the number put in parentheses at the right-hand edge of the text. Equations should be punctuated as if they were an ordinary part of the text. Punctuation appears after the equation but before the equation number, e.g.c2 = a2 + b2. (1)Literature ReferencesReferences are cited in the text just by square brackets [1]. (If square brackets are not available, slashes may be used instead, e.g. /2/.) Two or more references at a time may be put in one set of brackets [3,4]. The references are to be numbered in the order in which they are cited in the text and are to be listed at the end of the contribution under a heading References, see our example below. SummaryOn your CD, please indicate the format and word processor used. Please also provide your phone number, fax number and e-mail address for rapid communication with the publisher. Please always send your CD along with a hard copy that must match the CD’s content exactly. If you follow the foregoing, your paper will conform to the requirements of the publisher and facilitate a problem-free publication process.References[1] Dj.M. Maric, P.F. Meier and S.K. Estreicher: Mater. Sci. Forum Vol. 83-87 (1992), pp. 119-125[2] M.A. Green: High Efficiency Silicon Solar Cells (Trans Tech Publications, Switzerland 1987).[3] Y. Mishing, in: Diffusion Processes in Advanced Technological Materials, edtied by D. GuptaNoyes Publications/William Andrew Publising, Norwich, NY (2004), in press.[4] G. Henkelman, G.Johannesson and H. Jónsson, in: Theoretical Methods in Condencsed PhaseChemistry, edited by S.D. Schwartz, volume 5 of Progress in Theoretical Chemistry and Physics, chapter, 10, Kluwer Academic Publishers (2000).[5] R.J. Ong, J.T. Dawley and P.G. Clem: submitted to Journal of Materials Research (2003)[6] P.G. Clem, M. Rodriguez, J.A. Voigt and C.S. Ashley, U.S. Patent 6,231,666. (2001)[7] Information on 英文论文撰写格式说明1. 论文电子版制作均采用MS-Word软件2. 页面设置（操作—点击“文件”里的“页面设置”进行）1）新建WORD文档，选用A4纸并进行如下页面设置：2）页边距：上3cm，下1.7cm，左2cm，右2cm，装订线0cm。

What is the most important feature of Java?Java is a platform independent language.What do you mean by platform independence?Platform independence means that we can write andcompile the java code in one platform (eg Windows)and can execute the class in any other supportedplatform eg (Linux,Solaris,etc).What is a JVM?JVM is Java Virtual Machine which is a run timeenvironment for the compiled java class files.Are JVM's platform independent?JVM's are not platform independent. JVM's are platform specific run time implementation provided by thevendor.What is the difference between a JDK and a JVM?JDK is Java Development Kit which is for developmentpurpose and it includes execution environment also. But JVM is purely a run time environment and hence youwill not be able to compile your source files using a JVM.What is a pointer and does Java support pointers?Pointer is a reference handle to a memory location.Improper handling of pointers leads to memory leaksand reliability issues hence Java doesn't support theusage of pointers.7. What is the base class of all classes?ng.Object8. Does Java support multiple inheritance?Java doesn't support multiple inheritance.9. Is Java a pure object oriented language?Java uses primitive data types and hence is not apure object oriented language.10. Are arrays primitive data types?In Java, Arrays are objects.11. What is difference between Path and Classpath?Path and Classpath are operating system levelenvironment variales. Path is used define where thesystem can find the executables(.exe) files andclasspath is used to specify the location .class files. 12. What are local variables?Local varaiables are those which are declared withina block of code like methods. Local variables shouldbe initialised before accessing them.What are instance variables?Instance variables are those which are defined at theclass level. Instance variables need not be initializedbefore using them as they are automatically initialized to their default values.How to define a constant variable in Java?The variable should be declared as static and final. Soonly one copy of the variable exists for all instances of the class and the value can't be changed also.static final int MAX_LENGTH = 50; is an example forconstant.Should a main() method be compulsorily declared in all java classes?No not required. main() method should be defined only if the source class is a java application.What is the return type of the main() method?Main() method doesn't return anything hence declared void.Why is the main() method declared static?main() method is called by the JVM even before theinstantiation of the class hence it is declared as static.What is the arguement of main() method?main() method accepts an array of String object asarguement.19. Can a main() method be overloaded?Yes. You can have any number of main() methods with different method signature and implementation in the class.20. Can a main() method be declared final?Yes. Any inheriting class will not be able to have it'sown default main() method.21. Does the order of public and static declarationmatter in main() method?No. It doesn't matter but void should always comebefore main().22. Can a source file contain more than one classdeclaration?Yes a single source file can contain any number ofClass declarations but only one of the class can bedeclared as public.23. What is a package?Package is a collection of related classes andinterfaces. package declaration should be firststatement in a java class.24. Which package is imported by default?ng package is imported by default evenwithout a package declaration.Can a class declared as private be accessed outside it's package?Not possible.Can a class be declared as protected?The protected access modifier cannot be applied toclass and interfaces. Methods, fields can be declaredprotected, however methods and fields in a interfacecannot be declared protected.What is the access scope of a protected method?A protected method can be accessed by the classeswithin the same package or by the subclasses of theclass in any package.What is the purpose of declaring a variable as final?A final variable's value can't be changed. final variablesshould be initialized before using them.What is the impact of declaring a method as final?A method declared as final can't be overridden. A sub-class can't have the same method signature with adifferent implementation.I don't want my class to be inherited by any other class.What should i do?You should declared your class as final. But you can'tdefine your class as final, if it is an abstract class. A class declared as final can't be extended by any other class.31. Can you give few examples of final classesdefined in Java API?ng.String,ng.Math are final classes.32. How is final different from finally and finalize()?final is a modifier which can be applied to a class ora method or a variable. final class can't beinherited, final method can't be overriddenand final variable can't be changed.finally is an exception handling code section whichgets executed whether an exception is raised or notby the try block code segment.finalize() is a method of Object class which will be executed by the JVM just before garbage collectingobject to give a final chance for resource releasingactivity.33. Can a class be declared as static?We can not declare top level class as static, but onlyinner class can be declared static.publicclass Test{staticclass InnerClass{publicstaticvoid InnerMethod(){ System.out.println("Static InnerClass!"); }}publicstaticvoid main(String args[]){Test.InnerClass.InnerMethod();}}//output: Static Inner Class!34. When will you define a method as static?When a method needs to be accessed even beforethe creation of the object of the class then we shoulddeclare the method as static.35. What are the restriction imposed on a staticmethod or a static block of code?A static method should not refer to instance variableswithout creating an instance and cannot use "this"operator to refer the instance.36. I want to print "Hello" even before main() isexecuted. How will you acheive that?Print the statement inside a static block of code. Static blocks get executed when the class gets loaded intothe memory and even before the creation of an object.Hence it will be executed before the main()method.And it will be executed only once.What is the importance of static variable?static variables are class level variables where all objects of the class refer to the same variable. If one objectchanges the value then the change gets reflected in allthe objects.Can we declare a static variable inside a method?Static varaibles are class level variables and they can'tbe declared inside a method. If declared, the class willnot compile.What is an Abstract Class and what is it's purpose?A Class which doesn't provide complete implementationis defined as an abstract class. Abstract classes enforce abstraction.Can a abstract class be declared final?Not possible. An abstract class without being inherited is of no use and hence will result in compile time error.What is use of a abstract variable?Variables can't be declared as abstract. only classes and methods can be declared as abstract.Can you create an object of an abstract class?Not possible. Abstract classes can't be instantiated. 43. Can a abstract class be defined without anyabstract methods?Yes it's possible. This is basically to avoid instancecreation of the class.44. Class C implements Interface I containing methodm1 and m2 declarations. Class C has providedimplementation for method m2. Can i create anobject of Class C?No not possible. Class C should provideimplementation for all the methods in the InterfaceI. Since Class C didn't provide implementationfor m1 method, it has to be declared as abstract.Abstract classes can't be instantiated.45. Can a method inside a Interface be declared asfinal?No not possible. Doing so will result in compilationerror. public and abstract are the only applicable modifiers for method declaration in an interface. 46. Can an Interface implement another Interface?Intefaces doesn't provide implementation hence ainterface cannot implement another interface.47. Can an Interface extend another Interface?Yes an Interface can inherit another Interface, for that matter an Interface can extend more than oneInterface.48. Can a Class extend more than one Class?Not possible. A Class can extend only one class butcan implement any number of Interfaces.49. Why is an Interface be able to extend more thanone Interface but a Class can't extend more thanone Class?Basically Java doesn't allow multiple inheritance, so a Class is restricted to extend only one Class. But anInterface is a pure abstraction model and doesn'thave inheritance hierarchy like classes(do remember that the base class of all classes is Object). So anInterface is allowed to extend more than one Interface.50. Can an Interface be final?Not possible. Doing so so will result in compilationerror.51. Can a class be defined inside an Interface?Yes it's possible.52. Can an Interface be defined inside a class?Yes it's possible.53. What is a Marker Interface?An Interface which doesn't have any declarationinside but still enforces a mechanism.54. Which object oriented Concept is achieved byusing overloading and overriding?Polymorphism.Why does Java not support operator overloading?Operator overloading makes the code very difficult to read and maintain. To maintain code simplicity, Javadoesn't support operator overloading.Can we define private and protected modifiers forvariables in interfaces?No.What is Externalizable?Externalizable is an Interface that extendsSerializable Interface. And sends data into Streams in Compressed Format. It has two methods,writeExternal(ObjectOuput out) andreadExternal(ObjectInput in)What modifiers are allowed for methods in anInterface?Only public and abstract modifiers are allowed formethods in interfaces.What is a local, member and a class variable?Variables declared within a method are "local"variables.Variables declared within the class i.e not within any methods are "member" variables (global variables).Variables declared within the class i.e not within any methods and are defined as "static" are class variables.What is an abstract method?An abstract method is a method whose implementation is deferred to a subclass.∙What value does read() return when it has reached the end of a file?The read() method returns -1 when it has reached the end of a file.∙Can a Byte object be cast to a double value? No, an object cannot be cast to a primitive value.∙What is the difference between a static and anon-static inner class?A non-static inner class may have object instances that are associated with instances of the class's outer class. A static inner class does not have any object instances.∙What is an object's lock and which object's have locks?An object's lock is a mechanism that is used by multiple threads to obtain synchronized access to the object. A thread may execute a synchronized method of an object only after it has acquired the object's lock. All objects and classes have locks. A class's lock is acquired on the class's Class object.∙What is the % operator?It is referred to as the modulo or remainder operator. It returns the remainder of dividing the first operand by the second operand.∙When can an object reference be cast to an interface reference?An object reference be cast to an interface reference when the object implements the referenced interface. Which class is extended by all other classes?The Object class is extended by all other classes. Which non-Unicode letter characters may be used as the first character of an identifier?The non-Unicode letter characters $ and _ may appear as the first character of an identifierWhat restrictions are placed on method overloading?Two methods may not have the same name andargument list but different return types.What is casting?There are two types of casting, casting betweenprimitive numeric types and casting between objectreferences. Casting between numeric types is used to convert larger values, such as double values, tosmaller values, such as byte values. Casting between object references is used to refer to an object by acompatible class, interface, or array type reference.What is the return type of a program's main() method?void.If a variable is declared as private, where may thevariable be accessed?A private variable may only be accessed within theclass in which it is declared.73. What do you understand by private, protected andpublic?These are accessibility modifiers. Private is themost restrictive, while public is the least restrictive.There is no real difference between protected andthe default type (also known as package protected)within the context of the same package, however the protected keyword allows visibility to a derived classin a different package.74. What is Downcasting ?Downcasting is the casting from a general to a morespecific type, i.e. casting down the hierarchy75. What modifiers may be used with an inner classthat is a member of an outer class?A (non-local) inner class may be declared as public,protected, private, static, final, or abstract.76. How many bits are used to represent Unicode,ASCII, UTF-16, and UTF-8 characters?Unicode requires 16 bits and ASCII require 7 bitsAlthough the ASCII character set uses only 7 bits, it is usually represented as 8 bits.UTF-8 represents characters using 8, 16, and 18 bitpatterns.UTF-16 uses 16-bit and larger bit patterns.77. What restrictions are placed on the location of apackage statement within a source code file?A package statement must appear as the first line in asource code file (excluding blank lines andcomments).78. What is a native method?A native method is a method that is implemented in alanguage other than Java.What are order of precedence and associativity, andhow are they used?Order of precedence determines the order in whichoperators are evaluated in expressions. Associatitydetermines whether an expression is evaluated left-to-right or right-to-left.Can an anonymous class be declared asimplementing an interface and extending a class?An anonymous class may implement an interface orextend a superclass, but may not be declared to doboth.What is the range of the char type?The range of the char type is 0 to 216 - 1 (i.e. 0 to65535.)What is the range of the short type?The range of the short type is -(215) to 215 - 1. (i.e. -32,768 to 32,767)Why isn't there operator overloading?Because C++ has proven by example that operatoroverloading makes code almost impossible tomaintain.What does it mean that a method or field is "static"?Static variables and methods are instantiated onlyonce per class. In other words they are classvariables, not instance variables. If you change thevalue of a static variable in a particular object, thevalue of that variable changes for all instances of thatclass. Static methods can be referenced with thename of the class rather than the name of a particular object of the class (though that works too). That's how library methods like System.out.println() work. out is a static field in the ng.System class.85. Is null a keyword?The null value is not a keyword.86. Which characters may be used as the secondcharacter of an identifier, but not as the firstcharacter of an identifier?The digits 0 through 9 may not be used as the firstcharacter of an identifier but they may be used afterthe first character of an identifier.87. Is the ternary operator written x : y ? z or x ? y : z ?It is written x ?y : z.88. How is rounding performed under integer division?The fractional part of the result is truncated. This isknown as rounding toward zero.89. If a class is declared without any access modifiers,where may the class be accessed?A class that is declared without any access modifiersis said to have package access. This means that theclass can only be accessed by other classes andinterfaces that are defined within the same package. 90. Does a class inherit the constructors of itssuperclass?A class does not inherit constructors from any of itssuperclasses.Name the eight primitive Java types.The eight primitive types are byte, char, short, int,long, float, double, and boolean.What restrictions are placed on the values of eachcase of a switch statement?During compilation, the values of each case of aswitch statement must evaluate to a value that can be promoted to an int value.What is the difference between a while statement anda do while statement?A while statement checks at the beginning of a loop tosee whether the next loop iteration should occur. A do while statement checks at the end of a loop to seewhether the next iteration of a loop should occur. The do whilestatement will always execute the body of aloop at least once.What modifiers can be used with a local inner class?A local inner class may be final or abstract.When does the compiler supply a default constructorfor a class?The compiler supplies a default constructor for a class if no other constructors are provided.If a method is declared as protected, where may themethod be accessed?A protected method may only be accessed by classesor interfaces of the same package or by subclasses of the class in which it is declared.97. What are the legal operands of the instanceofoperator?The left operand is an object reference or null valueand the right operand is a class, interface, or arraytype.98. Are true and false keywords?The values true and false are not keywords.99. What happens when you add a double value to aString?The result is a String object.100. What is the diffrence between inner class and nested class?When a class is defined within a scope od anotherclass, then it becomes inner class. If the accessmodifier of the inner class is static, then it becomesnested class.101. Can an abstract class be final?An abstract class may not be declared as final. 102. What is numeric promotion?Numeric promotion is the conversion of a smallernumeric type to a larger numeric type, so that integer and floating-point operations may take place. Innumerical promotion, byte, char, and short values are converted to int values. The int values are alsoconverted to long values, if necessary. The long and float values are converted to double values, asrequired.What is the difference between a public and a non-public class?A public class may be accessed outside of itspackage. A non-public class may not be accessedoutside of its package.To what value is a variable of the boolean typeautomatically initialized?The default value of the boolean type is false.What is the difference between the prefix and postfix forms of the ++ operator?The prefix form performs the increment operation and returns the value of the increment operation. Thepostfix form returns the current value all of theexpression and then performs the incrementoperation on that value.What restrictions are placed on method overriding?Overridden methods must have the same name,argument list, and return type. The overriding method may not limit the access of the method it overrides.The overriding method may not throw any exceptions that may not be thrown by the overridden method.What is a Java package and how is it used?A Java package is a naming context for classes andinterfaces. A package is used to create a separatename space for groups of classes and interfaces.Packages are also used to organize related classes and interfaces into a single API unit and to controlaccessibility to these classes and interfaces.What modifiers may be used with a top-level class?A top-level class may be public, abstract, or final. 109. What is the difference between an if statement and a switch statement?The if statement is used to select among twoalternatives. It uses a boolean expression to decidewhich alternative should be executed. The switchstatement is used to select among multiplealternatives. It uses an int expression to determinewhich alternative should be executed.110. What are the practical benefits, if any, of importing a specific class rather than an entirepackage (e.g. import .* versus import.Socket)?It makes no difference in the generated class filessince only the classes that are actually used arereferenced by the generated class file. There isanother practical benefit to importing single classes,and this arises when two (or more) packages haveclasses with the same name.Take java.util.Timer and javax.swing.Timer, forexample. If I importjava.util.* and javax.swing.* and then try touse "Timer", I get an error while compiling (the classname is ambiguous between both packages). Let'ssay what you really wanted wasthe javax.swing.Timer class, and the only classes you plan on using in java.util are Collection andHashMap. In this case, some people will preferto import java.util.Collection and importjava.util.HashMap instead ofimporting java.util.*. This will now allow them touse Timer, Collection, HashMap, andother javax.swing classes without using fullyqualified class names in.111. Can a method be overloaded based on different return type but same argument type ?No, because the methods can be called without using their return type in which case there is ambiquity forthe compiler.112. What happens to a static variable that is defined within a method of a class ?Can't do it. You'll get a compilation error.113. How many static initializers can you have ?As many as you want, but the static initializers andclass variable initializers are executed in textual order and may not refer to class variables declared in theclass whose declarations appear textually after theuse, even though these class variables are in scope. 114. What is the difference between method overriding and overloading?Overriding is a method with the same name andarguments as in a parent, whereas overloading is the same method name but different arguments115. What is constructor chaining and how is it achieved in Java ?A child object constructor always first needs toconstruct its parent (which in turn calls its parentconstructor.). In Java it is done via an implicit call tothe no-args constructor as the first statement.116. What is the difference between the Boolean & operator and the && operator?If an expression involving the Boolean & operator isevaluated, both operands are evaluated. Then the &operator is applied to the operand. When anexpression involving the && operator is evaluated, the first operand is evaluated. If the first operand returnsa value of true then the second operand is evaluated.The && operator is then applied to the first andsecond operands. If the first operand evaluates tofalse, the evaluation of the second operand is skipped. 117. Which Java operator is right associative?The = operator is right associative.118. Can a double value be cast to a byte?Yes, a double value can be cast to a byte.119. What is the difference between a break statement and a continue statement?A break statement results in the termination of thestatement to which it applies (switch, for, do, or while).A continue statement is used to end the current loopiteration and return control to the loop statement. 120. Can a for statement loop indefinitely?Yes, a for statement can loop indefinitely. Forexample, consider the following: for(;;);To what value is a variable of the String typeautomatically initialized?The default value of an String type is null.What is the difference between a field variable and alocal variable?A field variable is a variable that is declared as amember of a class. A local variable is a variable thatis declared local to a method.How are this() and super() used with constructors?this() is used to invoke a constructor of the sameclass. super() is used to invoke a superclassconstructor.What does it mean that a class or member is final?A final class cannot be inherited. A final methodcannot be overridden in a subclass. A final fieldcannot be changed after it's initialized, and it mustinclude an initializer statement where it's declared.What does it mean that a method or class is abstract?An abstract class cannot be instantiated. Abstractmethods may only be included in abstract classes.However, an abstract class is not required to haveany abstract methods, though most of them do. Each subclass of an abstract class must override theabstract methods of its superclasses or it also should be declared abstract.What is a transient variable?Transient variable is a variable that may not beserialized.127. How does Java handle integer overflows and underflows?It uses those low order bytes of the result that can fitinto the size of the type allowed by the operation. 128. What is the difference between the >> and >>> operators?The >> operator carries the sign bit when shifting right.The >>> zero-fills bits that have been shifted out. 129. Is sizeof a keyword?The sizeof operator is not a keyword.What is the difference between a constructor and amethod?A constructor is a member function of a class that isused to create objects of that class. It has the samename as the class itself, has no return type, and isinvoked using the new operator.A method is an ordinary member function of a class. Ithas its own name, a return type (which may be void), and is invoked using the dot operator.What is the purpose of garbage collection in Java,and when is it used?The purpose of garbage collection is to identify anddiscard objects that are no longer needed by aprogram so that their resources can be reclaimed and reused.A Java object is subject to garbage collection when itbecomes unreachable to the program in which it isused.。

ACM错误提示、常见问题F.A.Q.<Chinese>我的程序为什么不能编译通过呢？Online Judge 要求C/C++程序符合Ansi标准：ANSI 标准和 Microsoft Visual C++ 存在一些不同的地方,比如：0>main函数必须声明为int ,也就是 void main<> 必须变成 int main<>VC同样可使用int main,只是程序最后需要 return 0;.1>Microsoft Visual C++ 可以将 main 函数声明为 void,而 ANSI 中必须为 int main2>请避免使用如下方式声明变量ifor <int i=0; i<10; i++>{...}您可以在For 语句之前,进行声明.3>itoa 不是一个 ANSI 函数4>stricmp 不是一个 ANSI 函数5>sqrt<> 的可能用法：sqrt<double <x>>; //强制转换为double6>OnlineJudge 中如何使用64位数？定义64位数使用 long long 类型,输出格式串中使用 %lld 表示64位数.虽然Free Pascal尽量设计得和Turbo Pascal接近,但是由于以下的两个原因,两者之间还是有一些区别的：1．Free Pascal是一个32位的编译器,而Turbo Pascal只是16位编译器；2．Free Pascal是一个跨平台的编译器,而Turbo Pascal只在windows上使用.如果你的代码是遵守ANSI Pascal的,那么代码从Turbo Pascal移植到Free Pascal是没有问题的.下面是在Turbo Pascal上可以使用,但是在Free Pascal就不能使用的一些语言特性：1．函数和过程在使用时,参数的类型必须和定义时完全一致.原因是在Free Pascal中添加了函数重载功能.2． PROTECTED,PUBLIC,PUBLISHED,TRY,FINALLY,EXCEPT,RAISE成为了关键字,因此不能作为函数和过程的名字.3． FAR,NEAR不再是关键字了.原因是Free Pascal是32位系统,不再需要这些关键字.4．布尔表达式不一定要全部进行计算.只要最终结果已经能够确定,就不再计算其它还没有计算的部分了.比如布尔表达式exp1 AND exp2 AND exp3,如果已知exp1的结果是false, 那么怎么表达式的结果肯定是false,exp2和exp3就不用进行计算了.5．在Free Pascal中,中的元素都是4个字节长的.6．表达式执行的顺序是不确定的.比如对于表达式a:=g<2>+f<3>; 不保证g<2>一定在f<3>之前执行.7．如果用Rewrite打开文件,那么文件就只能被写入了.如果需要读取这个文件,要对文件执行Reset.8． Free Pascal在程序结束之前一定要关闭输出文件,否则输出文件可能不能被正确的写入.9． Free Pascal理论上可以使用4GB的内存,因此实际上几乎可以使用系统中的所有剩余内存〔除非赛题中有内存限制〕.这是Free Pascal由于32位的编译器.但是对于Turbo Pascal来说,由于是16位的编译器,因此不能定义大小超过64KB的数据类型和变量,并且在DOS实模式下可以使用的内存总数只有640KB.Online Judge 评判结果分别表示什么意思？当你提交的程序被Online Judge评判完毕后,通常结果将立刻返回,或者你也可以在"Solutions"页看到评判结果.详细测试多数据测试模式下,将显示出各个测试数据的测试结果,并且无论结果如何,都会用所有测试数据进行测试.而一般多测试模式下,如果全对,则为Accepted；若其中某次数据出错,则评测中止,并返回此数据出错的信息.常见的Online Judge将评判结果分为如下几类：Accepted程序的输出完全满足题意,通过了全部的测试数据的测试.Wrong Answer你的程序顺利地运行完毕并正常退出,但是输出的结果却是错误的.注意：有的题包含多组测试数据,你的程序只要有一组数据是错误的,结果就是WA.Presentation Error你的程序输出的答案是正确的,但输出格式不对,比如多写了一些空格、换行.请注意,大部分程序的输出,都要求最终输出一个换行.不过,计算机程序是很难准确判断PE错误的,所以,很多PE错误都会被评判成WA.Compilation Error你的程序没有通过编译.你可以点击文字上的,查看详细的出错信息,对照此信息,可以找出出错原因.一般来说,这种错误主要是由 Linux 环境下相关编译器与你使用的本地编译器之间的差异造成的Judging我们正在运行你的程序进行测试,请稍候.Rejudging我们更新了测试数据或者评判程序,并且正在进行重测,这个过程比较耗费资源,请稍候.Time Limit Exceeded你的程序运行的时间超过了该题规定的最大时间,你的程序被Online Judge强行终止.注意：TE并不能说明你的程序的运行结果是对还是错,只能说明你的程序用了太多的时间.Memory Limit Exceeded.你的程序运行时使用的内存,超过了该题规定的最大限制,或者你的程序申请内存失败,你的程序将被Online Judge强行终止.注意：ML并不能说明你的程序的运行结果是对还是错,只能说明你的程序用了或者申请了太多的内存.Function Limit Exceeded你的程序运行时使用我们不允许使用的调用,将会得到此错误,诸如文件操作等相关函数.请特别注意：system<"PAUSE">; 也会导致此错误.Output Limit Exceeded你的程序输出了太多的东西.Online Judge规定提交的程序在运行的时候只能输出1024K字节的东西,如果你输出太多,将导致此错误.我们保证所有的题目的标准输出都小于1024K字节.Runtime Error你的程序出现了"运行时错误".大部分情况下,NKOJ系统将返回给你一个Runtime Error的编号,由SIG或FPE开头,后面跟随一个整数.具体的解释请点击此处查看.System Error系统发生了错误.由于异常因素导致系统没有正常运作.我们尽力保证系统的稳定运行,但如您遇此情况,请联系管理员.Online Judge 支持哪些编程语言？到目前为止,本 Online Judge 已经支持 C、C++、PASCAL、JAVA 编程语言如果题目包含多组测试数据,我应该在何时输出我的结果？OnlineJudge中,你的程序的输入和输出是相互的,因此,每当处理完一组测试数据,就应当按题目要求进行相应的输出操作.而不必将所有结果储存起来一起输出.GCC 中如何使用64位数？定义64位数使用 long long 类型,输出格式串中使用 %lld 表示64位数.关于本系统本系统内核部分孙威、王岩,WEB部分王岩.自主开发,保留一切权利.南开大学信息学院、南开大学ACM协会Runtime Error 代号介绍SIG <Signal,Linux系统信号> 部分：<4>SIGILL 执行了非法指令. 通常是因为可执行文件本身出现错误, 或者试图执行数据段.堆栈溢出时也有可能产生这个信号.<6>SIGABRT 程序自己发现错误并调用abort时产生.<6>SIGIOT 在PDP-11上由iot指令产生, 在其它机器上和SIGABRT一样.<7>SIGBUS 非法地址, 包括内存地址对齐<alignment>出错. eg: 访问一个四个字长的整数, 但其地址不是4的倍数.<8>SIGFPE 在发生致命的算术运算错误时发出. 不仅包括浮点运算错误, 还包括溢出与除数为0等其它所有的算术的错误.<11>SIGSEGV 试图访问未分配给自己的内存, 或试图往没有写权限的内存地址写数据.造成这种错误的原因有很多,主要原因有三条：3 / 5一、数据下标越界,包括越上界和越下界.二、堆栈溢出,比如递归层数过多.三、不恰当的指针使用.FPC <由Free Pascal 产生的错误代码>：由于OJ系统已经限制了程序的行为,所以以下部分代码并不会实际出现,此处列举仅仅为了文档相对完整.1 Invalid function number 错误的功能代码2 File not found 文件未找到3 Path not found 目录未发现4 Too many open files 打开太多的文件5 File access denied 文件访问拒绝6 Invalid file handle 错误的文件句柄12 Invalid file access code 错误的文件访问代码15 Invalid drive number 错误的驱动器数字16 Cannot remove current directory 不能移动当前目录17 Cannot rename across drives 不能跨越驱动器更改文件名100 Disk read error 磁盘读错误101 Disk write error 磁盘写错误102 File not assigned 文件未曾建立关联103 File not open 文件未打开104 File not open for input 文件不能打开读数据105 File not open for output 文件不能打开写数据106Invalid numeric format 错误的数字格式从标准输入<Text文件>中预期得到的数字格式不对.150 Disk is write-protected151 Bad drive request struct length152 Drive not ready154 CRC error in data156 Disk seek error157 Unknown media type158 Sector Not Found159 Printer out of paper160 Device write fault161 Device read fault162 Hardware failure200Division by zero被除数为0.201Range check error如果你编译你的程序时设置了方位检查,原因有可能是:数组访问超过了声明的范围.试图给一个变量赋值超过其范围<例如枚举类型>.202Stack overflow error栈溢出栈增长超过了最大值 <in which case the size of local variables should.be reduced to avoid this error>, or the stack has become corrupt. 只有当栈检查时才出现该错误.203Heap overflow error堆溢出堆增长超过了上界. This is caused when trying to allocate memory exlicitly with New, GetMem or ReallocMem, or when a class or object instance is created and no memory is left. Please note that, by default, Free Pascal provides a growing heap, i.e. the heap will try to allocate more memory if needed. However, if the heap has reached the maximum size allowed by the operating system or hardware, then you will get this error.204Invalid pointer operation错误的指针操作使用 Dispose or Freemem 时使用错误的指针 <特别的, Nil>205Floating point overflow浮点数上溢你试图使用或产生一个太大实数.206Floating point underflow你试图使用或产生一个太小实数.207Invalid floating point operation错误的浮点数操作可能是你开平方根或者对数时使用负数.210Object not initialized对象未初始化When compiled with range checking on, a program will report this error if you call a virtual method without having called istr constructor.211 Call to abstract method212 Stream registration error213 Collection index out of range214 Collection overflow error215Arithmetic overflow error 数字超出范围例如3000000000超出长整形范围216 General Protection fault217 Unhandled exception occurred219 Invalid typecast227 Assertion failed error5 / 5。

METHOD STATEMENTFORFIRE FIRHTING SYSTEMPROJECT NO. : 2240-2560 PROJECT NAME : STAR PROJECT CLIENT : STAR RAFİNERİ A.ŞSITE : TURKEYWe concluded the years’ experience of similar domestic and overseas projects and put forward this plan. Maybe there are some methods which are not applicable to the Star Project, and we will improve & revise it according to tender’s specification if our bidding will be accepted...1. PurposeThe main objective of this method statement is to describe in detail the sequence of work and make sure we can complete the project in time. This project has a heavy workload and the process of construction is also complicated, especially the Foam System, Deluge System and its supports clips. These works belong to work high above the ground and are easily affected by the wind climate of the sea, so the Fire Fighting System is a key point to the project that can be completed on time.2. ScopeThis document covers all Fire Fighting work (Including: fabrication, inspection, testing, cleaning, and erecting etc.)as detailed in AFC Drawings. Construction of fire line will be completed in accordance with the requirements detailed in this specification and STAR RAFİNERİ A.Ş drawings.The following are excluded from the scope of this document:2.1 Fabrication of pressure vessels and/or other mechanical pressure containingequipment unless specifically detailed in the applicable design documentation pertinent to the equipment.2.2 Fabrication of material handling devices and ducts2.3 Fabrication and/or assembly of instrumentation hook-ups and tube assemblies.2.4 GRP pipingNo deviation from this specification will be allowed without written approval from STAR RAFİNERİ A.Ş.3. ReferenceASME B31.1 Power pipingASME B16.5 Pipe flange and flange fittingASME B16.9 Factory-made wrought steel butt weldingASME B16.11 Forged steel Fittings, Socket –welding and ThreadedASME B16.20 Metallic Gaskets for pipe Flanges Ring-Joint Spiral-Wound, and JacketedASME B16.21 Non-metallic Flat Gaskets for pipe FlangesASME B16.34 Valves-Flanged, Threaded and welding EndASME B16.47 Large Diameter Steel FlangesASME B36.10M Welded and Seamless wrought steel pipeASME BPV VIII DIV.1 Rules for construction of pressure VesselsASME BPV V Non-destructive ExaminationASME BPV IX Welding and Brazing QualificationAPI526 Flanged steel safety Relief valvesAPI598 Valve Inspection and TestingAPI600 Bolted Bow net steel Gate valvesAPI607 Fire Test for soft seated Quarter-turn ValvesMSS SP25 Standard Marking System for Valves Flanges Fittings and Unions NFPA 100 Edition Fire Prevention CodeNFPA1000 06 Edition Standard for Fire Service Professional Qualifications Accreditation and Certification SystemsNFPA 101 06 Edition Life Safety Code, 2006 EditionNFPA 101A 01 Edition Guide on Alternative Approaches to Life SafetyNFPA 11 05 Edition Standard for Low-Expansion FoamNFPA 13 07 Edition Standard for the Installation of Sprinkler SystemsNFPA 16 03 Edition Standard for the Installation of Foam-Water Sprinkler and Foam-Water Spray Systems4. Planning and Deployment4.1 Construction Sequence: Technological process of construction is that first finishedthe work on the tank then completed the work above the ground.4.2 Spray line, support and painting should be prefabricated, welded and marked onthe ground.5. SHOP AND FIELD FABRICATION WORK5.1 GeneralAll drawing provided by STAR RAFİNERİ A.Ş, and this document will be adhered to in completing all fabrication activities.Where a discrepancy arises, SINOCONST will refer the discrepancy to STAR RAFİNERİ A.Ş for a written clarification prior to proceeding with the work in the affected area(s).Intermediate butt weld (BW) pipe joints are permitted for the purposes of maximizing available raw piping materials.Where lengths of ERW or EFW piping are joined at a butt weld, the longitudinal seams in adjoining lengths must be staggered. Where possible the longitudinal seams should be staggered in the top half of the pipe.A template will be used when laying out headers, mitres, laterals and otherirregular details to ensure accurate cutting and proper fit-up.In fitting up, prior to welding, spacers will be used so that a proper gap is made for the weld. Spacers will be removed prior to the commencement of welding.Pipe line-up clamps will be used. Tack welding of steel shapes to the pipe for line-up purposes is prohibited.The use of permanent backing rings or consumable inserts is prohibited.FW and FFW’s are detailed on isometric drawings, the Contractor will provide a minimum of 150mm extra length over the dimension nominated on the applicable isometric drawing.Branches will be made in accordance with piping isometric drawings, branch connection tables for line classes and standard drawings (where applicable).Materials will be in accordance with the material class data sheets.All sharp edges and burrs will be removed.5.2 Tolerances and Dimensional AccuracyFor butt welding of all piping components, pipe ends, fittings and weld neck flanges, the root opening and weld bevel alignment will be in accordance with ASME B31.3 and PFI-ES21.Linear and angular dimensional tolerances during fabrication will be in accordance with PFI-ES3.The inside surfaces of component ends to be joined by girth or mitre groove welds will be aligned to within the dimensional limits of the welding procedure.Flattening/ovality of the pipe will not exceed the requirements detailed in the applicable standard for the manufacturing process.5.3 Fitting-upFlange bolt holes are to be oriented as follows, unless otherwise indicated on the piping drawings.➢Flange bolt holes are to be oriented as follows, unless otherwise indicated on the piping drawings.⏹Flange face vertical - bolt holes to match vertical centerline.⏹Flange face horizontal - bolt holes to match north-south centerline.⏹Caution: The fitter will exercise care to ensure that required information isincluded on the shop drawings.When assembling flange connection, approval paste will be applied to the gasket and bolt/nut, except austenitic steel, for prevention of seizure, leakage, or adherence. Especially, for asbestos sheet gasket sufficient paste will be applied.5.4 Threaded ConnectionsAll pipe threads will be cut after any required bending, forming or heat treatment.Where this is not practical, suitable protection will be applied to protect the threads.All threaded connections will be gauge checked or chased after welding or heat treating.Openings for threaded thermowells and other inserts are to be drilled throughand be free from obstructions or burrs.Where threaded flanges are specified, the pipe will terminate 1.5mm short of the flange face.5.5 Specific Details for Galvanised Carbon Steel MaterialsAll aspects relating to fabrication, fabrication tolerances, cleaning and testing of galvanized piping and piping components will be the same as carbon steel pipe.No bolted type joints (i.e. flanged joints) will be assembled prior to hot-dip galvanizing.All spooled piping will be fabricated within an envelope size capable of being handled by the galvanizing plant/facility. The spool envelope size must be confirmed by the galvanizing plant prior to the start of fabrication.All fabricated piping will be left open and free of obstruction to enable full and proper pickling, fluxing and coating of all surfaces of the pipework.Where pipe supports and other attachments have been made to the piping, appropriate measures will be taken to ensure full and proper venting during pickling, fluxing and coating of all surfaces. This may include the provision of openings and weep holes of sufficient size on the attachment if they have not already been included in the attachment design. Some general guidelines governing this are presented in ASTM A385.Precautions will be taken to ensure minimal warpage and distortion of the piping during galvanizing operations. Guidelines on this are presented in ASTM A384.Where applicable, precautions relating to fabrication processes as detailed in ASTM A143 will be taken into account to protect against embrittlement of the galvanized coating.All pipe threads will be NPT type in accordance with ASME-B1.20.1.Threaded joints will not be assembled prior to hot-dip galvanizing.All threaded pipe and fittings will be inspected following hot-dip galvanizing to ensure that the thread form has not become overfilled with galvanizing metal.Where it is found that a thread form has become over filled with galvanizing metal, the thread form will be recut or cleaned with a tap and die set or similar machining technique.All recut threads will be coated with approved white spirit soluble rust preventive.5.6 Storage and HandlingAll openings in pipe work, whether vents or drains to atmosphere or openings for onsite hook up of modules etc., will be adequately sealed to prevent the ingress of foreign matter. End protectors applied will not be capable of passing into the bore of the pipe.Exposed machine surfaces such as weld bevels and flange facings will be covered with approved white spirit soluble rust preventive.Plastic end caps and thread protection plugs will be secured with an approved tape.Flange covers of metal (minimum 5mm thick) or wood (minimum 20mm thick) will be used, c/w gasket. The covers will be of the same outside diameter as the flange and held in place with 50% of the required bolts for the joint (minimum of 4 bolts). Covers held on with wire, steel or plastic straps are not acceptable.Pipe spools will be protected from damage and contamination during handling and storage. Piping items (e.g. spools and loose fittings) will be stacked to prevent excessive loading on each item. All pipe work will be examined to ensure that no deterioration has occurred during storage.Where stored on the ground in an unsheltered location, piping will be stacked up off the ground surface using dunnage or spacers in a location with good drainage and rainwater runoff.Silica gel will be placed inside spools to remove air humidity and reduce the onset of corrosion.All manually operated valves included in spools as part of the fabrication process (i.e. SW end valves) will be cycled from fully open to fully closed and back again to ensure operability. Gate and globe valves will be stored closed.Ball and plug valves will be positioned either fully open or fully closed, and diaphragm valves opened.Dissimilar metal piping and piping components will be segregated during storage, handling and transportation to avoid metal contamination and corrosion issues (i.e. stainless steel will not be stored or handled with carbon steel or galvanized components).Coated piping will be handled so as to avoid damage to the protective coating(s).6. Piping Installation6.1 Receival, Storage and HandlingPipe spools and valves will be protected from damage and contamination during handling and storage.Piping placed in storage will be stored off the ground using padded bolsters and plain timber under the uncoated ends.Suitable wedges will be used to preclude rolling.Pipe will be stored on flat well drained ground whenever possible.Piping items (eg spools, valves, loose fittings) will be stacked to prevent excessive loading on each item.All pipe work and valves will be examined to ensure that no deterioration has occurred in storage with particular attention to valve internals.Where not provided, silica gel will be placed inside spools to remove air humidity and reduce the onset of corrosion.Contamination of the surfaces of the pipes by corrosive or other detrimental substances, particularly non-ferrous metals, halogens and sulphur will be avoided.Adequate measures will be taken to prevent sulphur pick-up.Paint, markers labels or tools containing lead, copper, zinc or tin will not be used.All manually operated valves will be cycled from fully open to fully closed and back again to ensure operability.Adjacent valves and instruments will be protected against welding or cutting splatter.Gaskets will be stored in a warm dry enclosure, protected from direct sunlight.Gaskets will be kept clean and away from oil, grease, gasoline and solvents.Lifting and slinging operations will be carried out using nylon slings or straps.Metal chains and galvanised wire slings will not be used.6.2 Piping InstallationAll pipe will be installed in accordance with the Piping Design Criteria, Piping and Isometric Drawings, P&ID’s, Line Designation Table and Specification.Modifications necessary to remove interferences will be discussed and agreed with TECHNIP prior to any action by SINOCONST. All modifications will be noted on “as-built” drawings prepared by the SINOCONST.SINOCONST will use temporary supports where necessary, during assembly of the piping system/s, to ensure that no unacceptable stress or deformation occurs in the piping and connected equipment as a consequence of the cantilever effect of unsupported weight distribution.Special operations such as balancing will be completed under instructions submitted by the SINOCONST and approved by STAR RAFİNERİ A.Ş.All pipe work, valves, and piping specialty items will be inspected before installation to ensure that protective packing, covers, wrapping and internal protectives, such as silica gel bags etc are removed.Protective covers attached to piping and equipment will not be removed until immediately prior to installation.Any material soiled or damaged in the execution of the work will be thoroughly cleaned, repaired or replaced.Pipe internals will be free from mill scale, dirt and foreign material when installation is completed.On galvanized piping all damaged and exposed surfaces will be cleaned and prepared as per Specifications, and coated with an TECHNIP approved galvanizing method and/or compound.All closing FW or FFW’s on galvanized piping will have all surfaces affected by the welding operations cleaned and prepared as per Specifications, and coated with an STAR RAFİNERİ A.Ş approved galvanising method and/or compound.When a work period ceases before completion of all installation work scope, any open pipe ends will be protected with securely closed, tight fitting covers.Passageways, access ways, manholes, clean-outs, inspection points and reserved spaces will be kept unobstructed from piping and pipe fittings.6.3 Piping SupportPiping will be supported as indicated on the isometric drawings and piping support drawings. When temporary supports other than those shown on these drawings are required to facilitate installation, they will be of the removable type and will be indicated as such.Temporary supports will not transfer detrimental reactions/loads to piping, structural members, or equipment.Temporary supports will be completely removed upon completion of testing and prior to commissioning.Galvanized material will not be welded to austenitic stainless steels or nickel alloys under any circumstances.Where piping is supported using spring supports the locking pins will be in place during installation and hydrostatic testing the piping system. Locking pins/stops will be removed prior to system start-up.Spring supports will be installed to ensure that the identification, load and travel scales are readily visible.All threaded parts will be fully engaged, and locking nuts tightened.Variable spring and constant load hangers will be locked during the installation and assembly of the piping unless otherwise specified in the design instructions.If supports are unlocked for specially controlled operations such as balancing or cold pull, they will be relocked prior to any hydrostatic pressure tests and chemical cleaning.The installer will ensure that the load setting of spring supports is pre-set to the design requirements.If adjustment of the load is required, the installer will ensure adjustment does not prevent or reduce the anticipated support travel.Support for pipes larger than DN50 will not be located more than one pipe diameter from the specified position on the piping drawings. Where necessary, the fixing of the support to the structure will be adjusted to ensure that the orientation (direction, angle, etc) of the support is in accordance with the specified limits.。

目录一、数学问题 (4)1.精度计算——大数阶乘 (4)2.精度计算——乘法（大数乘小数） (4)3.精度计算——乘法（大数乘大数） (5)4.精度计算——加法 (6)5.精度计算——减法 (7)6.任意进制转换 (8)7.最大公约数、最小公倍数 (9)8.组合序列 (10)9.快速傅立叶变换（FFT） (10)10.Ronberg 算法计算积分 (12)11.行列式计算 (14)12.求排列组合数 (15)13.求某一天星期几 (15)14.卡特兰(Catalan) 数列原理 (16)15.杨辉三角 (16)16.全排列 (17)17.匈牙利算法----最大匹配问题 (18)18.最佳匹配KM 算法 (20)二、字符串处理 (22)1.字符串替换 (22)2.字符串查找 (23)3.字符串截取 (24)4.LCS-最大公共子串长度 (24)5.LCS-最大公共子串长度 (25)6.数字转换为字符 (26)三、计算几何 (27)1.叉乘法求任意多边形面积 (27)2.求三角形面积 (27)3.两矢量间角度 (28)4.两点距离（2D、3D） (28)5.射向法判断点是否在多边形内部 (29)6.判断点是否在线段上 (30)7.判断两线段是否相交 (31)8.判断线段与直线是否相交 (32)9.点到线段最短距离 (32)10.求两直线的交点 (33)11.判断一个封闭图形是凹集还是凸集 (34)12.Graham 扫描法寻找凸包 (35)13.求两条线段的交点 (36)四、数论 (37)1.x 的二进制长度 (37)2.返回x 的二进制表示中从低到高的第i 位 (38)3.模取幂运算 (38)4.求解模线性方程 (39)5.求解模线性方程组(中国余数定理) (39)6.筛法素数产生器 (40)7.判断一个数是否素数 (41)8.求距阵最大和 (42)8.求一个数每一位相加之和 (43)10.质因数分解 (43)11.高斯消元法解线性方程组 (44)五、图论 (45)1.Prim 算法求最小生成树................................................. 45 2.Dijkstra 算法求单源最短路径.. (46)3.Bellman-ford 算法求单源最短路径 (47)4.Floyd-Warshall 算法求每对节点间最短路径 (48)5.解欧拉图 (49)六、排序/查找 (50)1.快速排序 (50)2.希尔排序 (51)3.选择法排序 (52)4.二分查找 (52)七、数据结构 (53)1.顺序队列 (53)2.顺序栈 (56)3.链表 (59)4.链栈 (63)5.二叉树 (66)八、高精度运算专题 (68)1.专题函数说明 (68)2.高精度数比较 (69)3.高精度数加法 (69)4.高精度数减法 (70)5.高精度乘10 (71)6.高精度乘单精度 (71)7.高精度乘高精度 (72)8.高精度除单精度 (72)9.高精度除高精度 (73)九、标准模板库的使用 (74)1.计算求和 (74)2.求数组中的最大值 (76)3. sort 和qsort (76)十、其他 (78)1.运行时间计算 (78)DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD一、数学问题1.精度计算——大数阶乘语法：int result=factorial(int n);参数：n：n 的阶乘返回值：阶乘结果的位数注意：本程序直接输出n!的结果，需要返回结果请保留long a[] 需要math.h源程序：int factorial(int n){long a[10000];int i,j,l,c,m=0,w;a[0]=1;for(i=1;i<=n;i++){c=0;for(j=0;j<=m;j++){a[j]=a[j]*i+c;c=a[j]/10000;a[j]=a[j]%10000;}if(c>0) {m++;a[m]=c;}}w=m*4+log10(a[m])+1;printf("\n%ld",a[m]);for(i=m-1;i>=0;i--) printf("%4.4ld",a[i]);return w;}我也可以做到..5 / 782.精度计算——乘法（大数乘小数）语法：mult(char c[],char t[],int m);参数：c[]：被乘数，用字符串表示，位数不限t[]：结果，用字符串表示m：乘数，限定10 以内返回值：null注意：需要string.h源程序：void mult(char c[],char t[],int m){int i,l,k,flag,add=0;char s[100];l=strlen(c);for (i=0;i<l;i++)s[l-i-1]=c[i]-'0';for (i=0;i<l;i++){k=s[i]*m+add;if (k>=10) {s[i]=k%10;add=k/10;flag=1;} else{s[i]=k;flag=0;add=0;}}if (flag) {l=i+1;s[i]=add;} else l=i;for (i=0;i<l;i++)t[l-1-i]=s[i]+'0'; t[l]='\0';}3.精度计算——乘法（大数乘大数）语法：mult(char a[],char b[],char s[]);参数：a[]：被乘数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：null注意：空间复杂度为o(n^2)需要string.h源程序：void mult(char a[],char b[],char s[]){我也可以做到..6 / 78int i,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0; char result[65];alen=strlen(a);blen=strlen(b);for (i=0;i<alen;i++)for (j=0;j<blen;j++) res[i][j]=(a[i]-'0')*(b[j]-'0');for (i=alen-1;i>=0;i--){for (j=blen-1;j>=0;j--) sum=sum+res[i+blen-j-1][j]; result[k]=sum%10;k=k+1;sum=sum/10;}for (i=blen-2;i>=0;i--){for (j=0;j<=i;j++) sum=sum+res[i-j][j];result[k]=sum%10;k=k+1;sum=sum/10;}if (sum!=0) {result[k]=sum;k=k+1;}for (i=0;i<k;i++) result[i]+='0';for (i=k-1;i>=0;i--) s[i]=result[k-1-i];s[k]='\0';while(1){if (strlen(s)!=strlen(a)&&s[0]=='0')strcpy(s,s+1);elsebreak;}}4.精度计算——加法语法：add(char a[],char b[],char s[]);参数：a[]：被加数，用字符串表示，位数不限b[]：加数，用字符串表示，位数不限s[]：结果，用字符串表示返回值：null注意：空间复杂度为o(n^2)我也可以做到..7 / 78需要string.hDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD源程序：void add(char a[],char b[],char back[]){int i,j,k,up,x,y,z,l;char *c;if (strlen(a)>strlen(b)) l=strlen(a)+2; else l=strlen(b)+2; c=(char *) malloc(l*sizeof(char));i=strlen(a)-1;j=strlen(b)-1;k=0;up=0;while(i>=0||j>=0){if(i<0) x='0'; else x=a[i];if(j<0) y='0'; else y=b[j];z=x-'0'+y-'0';if(up) z+=1;if(z>9) {up=1;z%=10;} else up=0;c[k++]=z+'0';i--;j--;}if(up) c[k++]='1';i=0;c[k]='\0';for(k-=1;k>=0;k--)back[i++]=c[k];back[i]='\0';}5.精度计算——减法语法：sub(char s1[],char s2[],char t[]);参数：s1[]：被减数，用字符串表示，位数不限s2[]：减数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：null注意：默认s1>=s2，程序未处理负数情况需要string.h源程序：void sub(char s1[],char s2[],char t[])我也可以做到..8 / 78{int i,l2,l1,k;l2=strlen(s2);l1=strlen(s1);t[l1]='\0';l1--;for (i=l2-1;i>=0;i--,l1--){if (s1[l1]-s2[i]>=0)t[l1]=s1[l1]-s2[i]+'0';else{t[l1]=10+s1[l1]-s2[i]+'0';s1[l1-1]=s1[l1-1]-1;}}k=l1;while(s1[k]<0) {s1[k]+=10;s1[k-1]-=1;k--;}while(l1>=0) {t[l1]=s1[l1];l1--;}loop:if (t[0]=='0') {l1=strlen(s1);for (i=0;i<l1-1;i++) t[i]=t[i+1];t[l1-1]='\0';goto loop;}if (strlen(t)==0) {t[0]='0';t[1]='\0';}}6.任意进制转换语法：conversion(char s1[],char s2[],char t[]);参数：s[]：转换前的数字s2[]：转换后的数字d1：原进制数d2：需要转换到的进制数返回值：null注意：高于9 的位数用大写'A'～'Z'表示，2～16 位进制通过验证源程序：void conversion(char s[],char s2[],long d1,long d2){我也可以做到..9 / 78long i,j,t,num;char c;num=0;for (i=0;s[i]!='\0';i++){if (s[i]<='9'&&s[i]>='0') t=s[i]-'0'; else t=s[i]-'A'+10;num=num*d1+t;}i=0;while(1){t=num%d2;if (t<=9) s2[i]=t+'0'; else s2[i]=t+'A'-10;num/=d2;if (num==0) break;i++;}for (j=0;j<i/2;j++){c=s2[j];s2[j]=s[i-j];s2[i-j]=c;}s2[i+1]='\0';}7.最大公约数、最小公倍数语法：resulet=hcf(int a,int b)、result=lcd(int a,int b)参数：a：int a，求最大公约数或最小公倍数b：int b，求最大公约数或最小公倍数返回值：返回最大公约数（hcf）或最小公倍数（lcd）注意：lcd 需要连同hcf 使用源程序：int hcf(int a,int b){int r=0;while(b!=0){r=a%b;a=b;DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDb=r;}return(a);我也可以做到..10 / 78}lcd(int u,int v,int h){return(u*v/h);}8.组合序列语法：m_of_n(int m, int n1, int m1, int* a, int head)参数：m：组合数C 的上参数n1：组合数C 的下参数m1：组合数C 的上参数，递归之用*a：1～n 的整数序列数组head：头指针返回值：null注意：*a 需要自行产生初始调用时，m=m1、head=0调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0);源程序：void m_of_n(int m, int n1, int m1, int* a, int head){int i,t;if(m1<0 || m1>n1) return;if(m1==n1){return;}m_of_n(m,n1-1,m1,a,head); // 递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;m_of_n(m,n1-1,m1-1,a,head+1); // 再次递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;}9.快速傅立叶变换（FFT）语法：kkfft(double pr[],double pi[],int n,int k,double fr[],double fi[],intl,int il);参数：我也可以做到..11 / 78pr[n]：输入的实部pi[n]：数入的虚部n，k：满足n=2^kfr[n]：输出的实部fi[n]：输出的虚部l：逻辑开关，0 FFT，1 ifFTil：逻辑开关，0 输出按实部/虚部；1 输出按模/幅角返回值：null注意：需要math.h源程序：void kkfft(pr,pi,n,k,fr,fi,l,il)int n,k,l,il;double pr[],pi[],fr[],fi[];{int it,m,is,i,j,nv,l0; double p,q,s,vr,vi,poddr,poddi;for (it=0; it<=n-1; it++){m=it; is=0;for (i=0; i<=k-1; i++){j=m/2; is=2*is+(m-2*j); m=j;}fr[it]=pr[is]; fi[it]=pi[is];}pr[0]=1.0; pi[0]=0.0;p=6.283185306/(1.0*n);pr[1]=cos(p); pi[1]=-sin(p);if (l!=0) pi[1]=-pi[1];for (i=2; i<=n-1; i++){p=pr[i-1]*pr[1];q=pi[i-1]*pi[1];s=(pr[i-1]+pi[i-1])*(pr[1]+pi[1]);pr[i]=p-q; pi[i]=s-p-q;}for (it=0; it<=n-2; it=it+2){vr=fr[it]; vi=fi[it];fr[it]=vr+fr[it+1]; fi[it]=vi+fi[it+1];fr[it+1]=vr-fr[it+1]; fi[it+1]=vi-fi[it+1]; }m=n/2; nv=2;for (l0=k-2; l0>=0; l0--){我也可以做到..12 / 78m=m/2; nv=2*nv;for (it=0; it<=(m-1)*nv; it=it+nv)for (j=0; j<=(nv/2)-1; j++){p=pr[m*j]*fr[it+j+nv/2];q=pi[m*j]*fi[it+j+nv/2];s=pr[m*j]+pi[m*j];s=s*(fr[it+j+nv/2]+fi[it+j+nv/2]); poddr=p-q; poddi=s-p-q;fr[it+j+nv/2]=fr[it+j]-poddr;fi[it+j+nv/2]=fi[it+j]-poddi;fr[it+j]=fr[it+j]+poddr;fi[it+j]=fi[it+j]+poddi;}}if (l!=0)for (i=0; i<=n-1; i++){fr[i]=fr[i]/(1.0*n);fi[i]=fi[i]/(1.0*n);}if (il!=0)for (i=0; i<=n-1; i++){pr[i]=sqrt(fr[i]*fr[i]+fi[i]*fi[i]);if (fabs(fr[i])<0.000001*fabs(fi[i])) {if ((fi[i]*fr[i])>0) pi[i]=90.0;else pi[i]=-90.0;}DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDelsepi[i]=atan(fi[i]/fr[i])*360.0/6.283185306;}return;}10.Ronberg 算法计算积分语法：result=integral(double a,double b);参数：a：积分上限b：积分下限我也可以做到..13 / 78function f：积分函数返回值：f 在（a,b）之间的积分值注意：function f(x)需要自行修改，程序中用的是sina(x)/x 需要math.h默认精度要求是1e-5源程序：double f(double x){return sin(x)/x; //在这里插入被积函数}double integral(double a,double b){double h=b-a;double t1=(1+f(b))*h/2.0;int k=1;double r1,r2,s1,s2,c1,c2,t2;loop:double s=0.0;double x=a+h/2.0;while(x<b){s+=f(x);x+=h;}t2=(t1+h*s)/2.0;s2=t2+(t2-t1)/3.0;if(k==1){k++;h/=2.0;t1=t2;s1=s2;goto loop;}c2=s2+(s2-s1)/15.0;if(k==2){c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto loop;}r2=c2+(c2-c1)/63.0;if(k==3){r1=r2; c1=c2;k++;h/=2.0;t1=t2;s1=s2;我也可以做到..14 / 78goto loop;}while(fabs(1-r1/r2)>1e-5){ r1=r2;c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto loop;}return r2;}11.行列式计算语法：result=js(int s[][],int n)参数：s[][]：行列式存储数组n：行列式维数，递归用返回值：行列式值注意：函数中常数N 为行列式维度，需自行定义源程序：int js(s,n)int s[][N],n;{int z,j,k,r,total=0;int b[N][N];/*b[N][N]用于存放，在矩阵s[N][N]中元素s[0]的余子式*/if(n>2){for(z=0;z<n;z++){for(j=0;j<n-1;j++)for(k=0;k<n-1;k++)if(k>=z) b[j][k]=s[j+1][k+1]; elseb[j][k]=s[j+1][k];if(z%2==0) r=s[0][z]*js(b,n-1); /*递归调用*/else r=(-1)*s[0][z]*js(b,n-1);total=total+r;}}else if(n==2)total=s[0][0]*s[1][1]-s[0][1]*s[1][0];return total;我也可以做到..15 / 78}12.求排列组合数语法：result=P(long n,long m); / result=long C(long n,long m);参数：m：排列组合的上系数n：排列组合的下系数返回值：排列组合数注意：符合数学规则：m<＝n源程序：long P(long n,long m){long p=1;while(m!=0){p*=n;n--;m--;}return p;}long C(long n,long m){long i,c=1;DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDi=m;while(i!=0){c*=n;n--;i--;}while(m!=0){c/=m;m--;}return c;}13.求某一天星期几语法：result=weekday(int N,int M,int d)参数：N,M,d：年月日，例如：2003,11,4返回值：0：星期天，1 星期一……注意：需要math.h适用于1582 年10 月15 日之后, 因为罗马教皇格里高利十三世在这一天启用新历法.源程序：我也可以做到..16 / 78int weekday(int N,int M,int d){int m,n,c,y,w;m=(M-2)%12;if (M>=3) n=N;else n=N-1;c=n/100;y=n%100;w=(int)(d+floor(13*m/5)+y+floor(y/4)+floor(c/4)-2*c)%7;while(w<0) w+=7;return w;}14.卡特兰(Catalan) 数列原理令h(1)＝1，catalan 数满足递归式：h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)该递推关系的解为：h(n)=c(2n-2,n-1)/n (n=1,2,3,...)1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420,24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …1.括号化问题。

ACM的论⽂写作格式标准ACM Word Template for SIG Site1st Author1st author's affiliation1st line of address2nd line of address Telephone number, incl. country code 1st author's E-mail address2nd Author2nd author's affiliation1st line of address2nd line of addressTelephone number, incl. country code2nd E-mail3rd Author3rd author's affiliation1st line of address2nd line of addressTelephone number, incl. country code3rd E-mailABSTRACTA s network speed continues to grow, new challenges of network processing is emerging. In this paper we first studied the progress of network processing from a hardware perspective and showed that I/O and memory systems become the main bottlenecks of performance promotion. Basing on the analysis, we get the conclusion that conventional solutions for reducing I/O and memory accessing latencies are insufficient for addressing the problems.Motivated by the studies, we proposed an improved DCA combined with INIC solution which has creations in optimized architectures, innovative I/O data transferring schemes and improved cache policies. Experimental results show that our solution reduces 52.3% and 14.3% cycles on average for receiving and transmitting respectively. Also I/O and memory traffics are significantly decreased. Moreover, an investigation to the behaviors of I/O and cache systems for network processing is performed. And some conclusions about the DCA method are also presented.KeywordsKeywords are your own designated keywords.1.INTRODUCTIONRecently, many researchers found that I/O system becomes the bottleneck of network performance promotion in modern computer systems [1][2][3]. Aim to support computing intensive applications, conventional I/O system has obvious disadvantages for fast network processing in which bulk data transfer is performed. The lack of locality support and high latency are the two main problems for conventional I/O system, which have been wildly discussed before [2][4].To overcome the limitations, an effective solution called Direct Cache Access (DCA) is suggested by INTEL [1]. It delivers network packages from Network Interface Card (NIC) into cache instead of memory, to reduce the data accessing latency. Although the solution is promising, it is proved that DCA is insufficient to reduce the accessing latency and memory traffic due to many limitations [3][5]. Another effective solution to solve the problem is Integrated Network Interface Card (INIC), which is used in many academic and industrial processor designs [6][7]. INIC is introduced to reduce the heavy burden for I/O registers access in Network Drivers and interruption handling. But recent report [8] shows that the benefit of INIC is insignificant for the state of the art 10GbE network system.In this paper, we focus on the high efficient I/O system design for network processing in general-purpose-processor (GPP). Basing on the analysis of existing methods, we proposed an improved DCA combined with INIC solution to reduce the I/O related data transfer latency.The key contributions of this paper are as follows:Review the network processing progress from a hardware perspective and point out that I/O and related last level memory systems have became the obstacle for performance promotion.Propose an improved DCA combined with INIC solution for I/O subsystem design to address the inefficient problem of a conventional I/O system.Give a framework of the improved I/O system architecture and evaluate the proposed solution with micro-benchmarks. Investigate I/O and Cache behaviors in the network processing progress basing on the proposed I/O system.The paper is organized as follows. In Section 2, we present the background and motivation. In Section 3, we describe the improved DCA combined INIC solution and give a framework of the proposed I/O system implementation. In Section 4, firstly we give the experiment environment and methods, and then analyze the experiment results. In Section 5, we show some related works. Finally, in Section 6, we carefully discuss our solutions with many existing technologies, and then draw some conclusions.2.Background and MotivationIn this section, firstly we revise the progress of network processing and the main network performance improvement bottlenecks nowadays. Then from the perspective of computer architecture, a deep analysis of network system is given. Also the motivation of this paper is presented.2.1Network processing reviewFigure 1 illustrates the progress of network processing. Packages from physical line are sampled by Network Interface Card (NIC). NIC performs the address filtering and stream control operations, then send the frames to the socket buffer and notifiesOS to invoke network stack processing by interruptions. When OS receives the interruptions, the network stack accesses the data in socket buffer and calculates the checksum. Protocol specific operations are performed layer by layer in stack processing. Finally, data is transferred from socket buffer to the user buffer depended on applications. Commonly this operation is done by memcpy, a system function in OS.Figure 1. Network Processing FlowThe time cost of network processing can be mainly broke down into following parts: Interruption handling, NIC driver, stack processing, kernel routine, data copy, checksum calculation and other overheads. The first 4 parts are considered as packet cost, which means the cost scales with the number of network packets. The rests are considered as bit cost (also called data touch cost), which means the cost is in proportion to the total I/O data size. The proportion of the costs highly depends on the hardware platform and the nature of applications. There are many measurements and analyses about network processing costs [9][10]. Generally, the kernel routine cost ranges from 10% - 30% of the total cycles; the driver and interruption handling costs range from 15% - 35%; the stack processing cost ranges from 7% - 15%; and data touch cost takes up 20% - 35%. With the development of high speed network (e.g. 10/40 Gbps Ethernet), an increasing tendency for kernel routines, driver and interruption handling costs is observed [3].2.2 MotivationTo reveal the relationship among each parts of network processing, we investigate the corresponding hardware operations. From the perspective of computer hardware architecture, network system performance is determinedby three domains: CPU speed, Memory speed and I/O speed. Figure 2 depicts the relationship.Figure 2. Network xxxxObviously, the network subsystem can achieve its maximal performance only when the three domains above are in balance. It means that the throughput or bandwidth of each hardware domain should be equal with others. Actually this is hard for hardware designers, because the characteristics and physical implementation technologies are different for CPU, Memory and I/O system (chipsets) fabrication. The speed gap between memory and CPU –a.k.a “the memory wall” –has been paid special attention for more than ten years, but still it is not well addressed. Also the disparity between the data throughput inI/O system and the computing capacity provided by CPU has been reported in recent years [1][2].Meanwhile, it is obvious that the major time costs of network processing mentioned above are associated with I/O and Memory speeds, e.g. driver processing, interruption handling, and memory copy costs. The most important nature of network processing is the “producer-consumer locality” between every two consecutive steps of the processing flow. That means the data produced in one hardware unit will be immediately accessed by another unit, e.g. the data in memory which transported from NIC will be accessed by CPU soon. However for conventional I/O and memory systems, the data transfer latency is high and the locality is not exploited.Basing on the analysis discussed above, we get the observation that the I/O and Memory systems are the limitations for network processing. Conventional DCA or INIC cannot successfully address this problem, because it is in-efficient in either I/O transfer latency or I/O data locality utilization (discussed in section 5). To diminish these limitations, we present a combined DCA with INIC solution. The solution not only takes the advantages of both method but also makes many improvements in memory system polices and software strategies.3.Design MethodologiesIn this section, we describe the proposed DCA combined with INIC solution and give a framework of the implementation. Firstly, we present the improved DCA technology and discuss the key points of incorporating it into I/O and Memory systems design. Then, the important software data structures and the details of DCA scheme are given. Finally, we introduce the system interconnection architecture and the integration of NIC.3.1Improved DCAIn the purpose of reducing data transfer latency and memory traffic in system, we present an improved Direct Cache Access solution. Different with conventional DCA scheme, our solution carefully consider the following points.The first one is cache coherence. Conventionally, data sent from device by DMA is stored in memory only. And for the same address, a different copy of data is stored in cache which usually needs additional coherent unit to perform snoop operation [11]; but when DCA is used, I/O data and CPU data are both stored in cache with one copy for one memory address, shown in figure 4. So our solution modifies the cache policy, which eliminated the snooping operations. Coherent operation can be performed by software when needed. This will reduce much memory traffic for the systems with coherence hardware [12].I/O writeCPU write*(addr) = aCacheCPU write*(addr) = aI/O write with DCA*(addr) = bCache(a) cache coherance withconventional I/O(b) cache coherance withDCA I/OFigure 3. xxxxThe second one is cache pollution. DCA is a mixed blessing to CPU: On one side, it accelerates the data transfer; on the other side, it harms the locality of other programs executed in CPU and causes cache pollution. Cache pollution is highly depended on the I/O data size, which is always quite large. E.g. one Ethernet package contains a maximal 1492 bytes normal payload and a maximal 65536 bytes large payload for Large Segment Offload (LSO). That means for a common network buffer (usually 50 ~ 400 packages size), a maximal size range from 400KB to 16MB data is sent to cache. Such big size of data will cause cache performance drop dramatically. In this paper, we carefully investigate the relationship between the size of I/O data sent by DCA and the size of cache system. To achieve the best cache performance, a scheme of DCA is also suggested in section 4. Scheduling of the data sent with DCA is an effective way to improve performance, but it is beyond the scope of this paper.The third one is DCA policy. DCA policy refers the determination of when and which part of the data is transferred with DCA. Obviously, the scheme is application specific and varies with different user targets. In this paper, we make a specific memory address space in system to receive the data transferred with DCA. The addresses of the data should be remapped to that area by user or compilers.3.2DCA Scheme and detailsTo accelerate network processing, many important software structures used in NIC driver and the stack are coupled with DCA. NIC Descriptors and the associated data buffers are paid special attention in our solution. The former is the data transfer interface between DMA and CPU, and the later contains the packages. For farther research, each package stored in buffer is divided into the header and the payload. Normally the headers are accessed by protocols frequently, but the payload is accessed only once or twice(usually performed as memcpy) in modern network stack and OS. The details of the related software data structures and the network processing progress can be found in previous works [13].The progress of transfer one package from NIC to the stack with the proposed solution is illustrated in Table 1. All the accessing latency parameters in Table 1 are based on a state of the art multi-core processor system [3]. One thing should be noticed is that the cache accessing latency from I/O is nearly the same with that from CPU. But the memory accessing latency from I/O is about 2/3 of that from CPU due to the complex hardware hierarchy above the main memory.Table 1. Table captions should be placed above the tabletransfer.We can see that DCA with INIC solution saves above 95% CPU cycles in theoretical and avoid all the traffic to memory controller. In this paper, we transfer the NIC Descriptors and the data buffers including the headers and payload with DCA to achieve the best performance. But when cache size is small, only transfer the Descriptors and the headers with DCA is an alternative solution.DCA performance is highly depended on system cache policy. Obviously for cache system, write-back with write-allocate policy can help DCA achieves better performance than write-through with write non-allocate policy. Basing on the analysis in section 3.1, we do not use the snooping cache technology to maintain the coherence with memory. Cache coherence for other non-DCA I/O data transfer is guaranteed by software.3.3 On-chip network and integrated NICFootnotes should be Times New Roman 9-point, and justified to the full width of the column.Use the “ACM Reference format” for references – that is, a numbered list at the end of the article, ordered alphabetica lly and formatted accordingly. Seeexamplesof sometypicalreference types, in the new “ACM Reference format”, at the end of this document. Within this template, use the style named references for the text. Acceptable abbreviations, for journal names, can be found here:/doc/4a4372fc0242a8956bece471.html /reference/abbreviations/. Word may try to automatically …underline? hotlinks in your references, the correct style is NO underlining.The references are also in 9 pt., but that section (see Section 7) is ragged right. References should be published materials accessible to the public. Internal technical reports may be cited only if they are easily accessible (i.e. you can give the address to obtain the report within your citation) and may be obtained by any reader. Proprietary information may not be cited. Private communications should be acknowledged, not referenced (e.g., “[Robertson, personal communication]”).3.4 Page Numbering, Headers and FootersDo not include headers, footers or page numbers in your submission. These will be added when the publications are assembled.4. FIGURES/CAPTIONSPlace Tables/Figures/Images in text as close to the reference as possible (see Figure 1). It may extend across both columns to a maximum width of 17.78 cm (7”).Captions should be Times New Roman 9-point bold. They should be numbered (e.g., “Table 1” or “Figure 2”), please note that the word for Table and Figure are spelled out. Figure?s captions should be centered beneath the image or picture, and Table captions should be centered above the table body.5. SECTIONSThe heading of a section should be in Times New Roman 12-point bold in all-capitals flush left with an additional 6-points of white space above the section head. Sections and subsequent sub- sections should be numbered and flush left. For a section head andFigure 1. Insert caption to place caption below figure.a subsection head together (such as Section 3 and subsection 3.1), use no additional space above the subsection head.5.1SubsectionsThe heading of subsections should be in Times New Roman 12-point bold with only the initial letters capitalized. (Note: For subsections and subsubsections, a word like the or a is not capitalized unless it is the first word of the header.)5.1.1SubsubsectionsThe heading for subsubsections should be in Times New Roman 11-point italic with initial letters capitalized and 6-points of white space above the subsubsection head.5.1.1.1SubsubsectionsThe heading for subsubsections should be in Times New Roman 11-point italic with initial letters capitalized.5.1.1.2SubsubsectionsThe heading for subsubsections should be in Times New Roman 11-point italic with initial letters capitalized.6.ACKNOWLEDGMENTSOur thanks to ACM SIGCHI for allowing us to modify templates they had developed.7.REFERENCES[1]R. Huggahalli, R. Iyer, S. Tetrick, "Direct Cache Access forHigh Bandwidth Network I/O", ISCA, 2005.[2] D. Tang, Y. Bao, W. Hu et al., "DMA Cache: Using On-chipStorage to Architecturally Separate I/O Data from CPU Data for Improving I/O Performance", HPCA, 2010.[3]Guangdeng Liao, Xia Zhu, Laxmi Bhuyan, “A New ServerI/O Architecture for High Speed Networks,” HPCA, 2011. [4] E. A. Le′on, K. B. Ferreira, and A. B. Maccabe. Reducing the Impact of the MemoryWall for I/O Using Cache Injection, In 15th IEEE Symposium on High-Performance Interconnects (HOTI?07), Aug, 2007.[5] A.Kumar, R.Huggahalli, S.Makineni, “Characterization ofDirect Cache Access on Multi-core Systems and 10GbE”,HPCA, 2009.[6]Sun Niagara 2,/doc/4a4372fc0242a8956bece471.html /processors/niagara/index.jsp [7]PowerPC[8]Guangdeng Liao, L.Bhuyan, “Performance Measurement ofan Integrated NIC Architecture with 10GbE”, 17th IEEESymposium on High Performance Interconnects, 2009. [9] A.Foong et al., “TCP Performance Re-visited,” IEEE Int?l Symp on Performance Analysis of Software and Systems,Mar 2003[10]D.Clark, V.Jacobson, J.Romkey, and H.Saalwen. “AnAnalysis of TCP processing overhead”. IEEECommunications,June 1989.[11]J.Doweck, “Inside Intel Core microarchitecture and smartmemory access”, Intel White Paper, 2006[12]Amit Kumar, Ram Huggahalli., Impact of Cache CoherenceProtocols on the Processing of Network Traffic[13]Wenji Wu, Matt Crawford, “Potential performancebottleneck in Linux TCP”, International Journalof Communication Systems, Vol. 20, Issue 11, pages 1263–1283, November 2007.[14]Weiwu Hu, Jian Wang, Xiang Gao, et al, “Godson-3: ascalable multicore RISC processor with x86 emulation,” IEEE Micro, 2009. 29(2): pp. 17-29.[15]Cadence Incisive Xtreme Series./doc/4a4372fc0242a8956bece471.html /products/sd/ xtreme_series. [16]Synopsys GMAC IP. /doc/4a4372fc0242a8956bece471.html /dw/dwtb.php?a=ethernet_mac[17]/doc/4a4372fc0242a8956bece471.html ler, P.M.Watts, A.W.Moore, "Motivating Future Interconnects: A Differential Measurement Analysis of PCI Latency", ANCS, 2009.[18]Nathan L.Binkert, Ali G.Saidi, Steven K.Reinhardt.Integrated Network Interfaces for High-Bandwidth TCP/IP.Proceedings of the 12th international conferenceon Architectural support for programming languages andoperating systems (ASPLOS). 2006[19]G.Liao, L.Bhuyan, "Performance Measurement of anIntegrated NIC Architecture with 10GbE", HotI, 2009. [20]Intel Server Network I/O Acceleration./doc/4a4372fc0242a8956bece471.html /technology/comms/perfnet/download/ServerNetworkIOAccel.pdfColumns on Last Page Should Be Made As Close AsPossible to Equal Length。