” AMATH 483编程设计 写作、C++编程调试Problem Set #2 AMATH 483/583 High-Performance Scientific Computing Copyright 2020-2021, Andrew Lumsdaine. Created using Sphinx 3.5.3.Table of Contents Problem Set #2Problem Set #2Assigned: Apr 6, 2021Due: Apr 13, 20211 BackgroundCourse Lectures 3, 4, and 5. You only need to watch lecture 5 up through the point theMatrix class is presented. We will start next week with the CPU model. You may alsowant to watch the material on const at 2X speed there is quite a bit of detail and itwill be important but it is not the focus of this assignment (which is to start writingmathematical C++);Walkthrough 2 IntroductionStarting with this assignment, we Will be building up a small library of high-performancelinear algebra functionality both performance and functionality will be built up insuccessive assignments this quarter. In this assignment we will be developing somefunctions for working with vectors (as defined by the Vector class we developed inlecture).Vectors are fundamental to scientific computing. As we explore increasingly large-scalecomputing platforms, we will be revisiting how to carry out Vector functionality to takeadvantage of performance opportunities. We will do the same with the Matrix classand sparse matrix classes that we Will develop in the coming weeks.In addition, we will look at some of the particular aspects of writing a function,supporting separate compilation, and how to automate the compilation process.3 PreliminariesIn Lecture 4 we introduced vector spaces – sets of objects that obeyed certainproperties with respect to addition and with respect to scalar multiplication.What that definition did not include was any way to measure the size of a vector.Measuring the size of a Vector also gives us a way to measure the distance betweentwo vectors; since the difference between two vectors is also a vector, being able tomeasure the size of a vector also lets us measure the distance between them.2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 2/21In plane geometry, points in the plane are represented as pairs of numbers, and it isfairly easy to verify the vector space properties with pairs and see that pairs ofnumbers can represent a vector space.The figure below illustrates how we customarily think about measuring distances in theplane.That is, for a vector represented as the pair ,the length of that vector, i.e., its distance from the origin, isWe can generalize that notion of distance to -tuples of numbers ( -dimensionalvectors) in the following way. Let the vector be the -tuple of real numbersWe use the shorthand for saying that is an -tuple of real numbers with the notationThen, the distance of the vector to the origin isDistance expressed as is called a norm and the 2-norm above is also called theEuclidean norm (in analogy to the plane geometry interpretation of distance).There are two other common norms in numerical linear algebra that can also provideuseful notions of distance, respectively the 1-norm and the infinity (or max) norm:2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 3/21(A vector space with a norm is called a normed vector space; if the vector space iscomplete in the norm, it is called a Banach space. If the norm is defined by an innerproduct, it is called a Hilbert space.)As with the definition we had in lecture about vector spaces, any functioncan be a norm on a vector space , Provided it satisfies certain properties:The interested reader can verify that the 1-norm, 2-norm, and infinity norm definedabove satisfy these properties.3.1 More on Visual Studio CodeIf you are interested in making better use of Visual Studio Code, Microsoft has anumber of tutorials on-line about how to use some of its various features:Visual Studio Code Documentation Home Using Clang in Visual Studio Code Integrate with External Tools via Tasks I particularly encourage you to explore using Intellisense and how to compile, finderrors, and debug from within VS Code.4 Warm Up4.1 Extract the homework filesWe will be using files as data input and output mechanisms for the computationalcapabilities we will be developing. As is customary with large software libraries, we willfactor the software into multiple files. Regardless of the size of a software project, wewill want to start automating The compilation process using make. (As the courseprogresses we will also be introducing more advanced features of make.)Create a new subdirectory named ps2 to hold your files for this assignment. The filesfor this assignment are in a tar ball that can be downloaded with this link .||x|| = | | and ||x| = | |. 1 i=0N1xi | maxixif : V RVf(x) 0 for all x Vf(x + y) f(x) + f(y) for all x, y Vf(x) = ||f(x) for all : C and x Vf(x) = 0 if and only if x = 02021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 4/21To extract the files for this assignment, download the tar ball and copy it (or move it) toyour ps2 subdirectory. From a shell program, change your working directory to be theps2 subdirectory and execute the commandThis will extract all of the files that are contained in ps2.tar.gz. (Tar files are very muchlike zip files or other files built by programs that bundle multiple files together into one.The name tar is originally derived from tape archive.)The files that should be extracted from the tape archive file areMakefileVector.hpp contains the declaration of the Vector class as developed in lecture4Matrix.hpp contains the declaration of the Matrix class as developed in lecture5amath583.hpp contains declarations for the functions defined in amath583.cppamath583.cpp contains assorted operations on Vectors and Matricescatch.hpp header file for the Catch2 testing frameworkCImg.h – header file for CImg image library, used by julia.cppjulia.cpp main file for julia.exeQuestions.rst – text file for short-answer questionstest_*.cpp files to test the programs you will be writingverify.bash – bash script to build and run all test programs4.2 MakeThe Makefile provided to you Has rules for building the various executables in thisassignment. As mentioned in lecture, Makefiles contain these rules, but make alsosupports a simple macro language. We can use this language to achieve similar goalsas with any programming language to automate repetitive manual tasks, makingthem repeatable and consistent.The ability to define and use macros is one of the most basic, but most powerful,aspects of make. Consider a rule such as one we presented in lecture:$ tar zxvf ps2.tar.gz2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 5/21This rule will invoke the compilation step with the c++ compiler to build amath583.o.But note that this rule is extremely specific. The compiler must be named c++ . If thereare other flags that are needed, such as an include path or library, we would have toadd those:Again, the paths would have to be exactly the ones specified. That would be fine forbuilding just one Program in one environment. But suppose, say, you wanted to be ableto build multiple Executables using the same Makefile. You would need to copy thesame paths and compiler name for every executable. More problematically, supposeyou want to make these same programs in different environments, where the compilermight have a different name, or the paths might have different names. In that case, youwould have to manually Edit each line to put in the right compiler name, right paths, etc and you would have to do this every time you changed environments. And everytime you do something manually, there is the opportunity to introduce errors. Suddenly,the automation and ease promised by make doesnt seem like such a big win.This is where abstractions comes to the rescue (as it always does) in this case, in theform of macros. Rather than specifying what compiler we actually want to use, or whatcompiler flags we pass to it, we can write our rules using placeholders:Make will substitute whatever we define CXX to be where it sees $(CXX) and substitutewhatever we define CXXFLAGS to be where it sees $(CXXFLAGS) . Now when we write rulesusing $(CXX) we are writing generic rules that can be made specific by how we set CXXet al.Try the following experiment in your ps2 directory. First, executeamath583.o : amath583.cpp amath583.hpp Vector.hppc++ -c amath583.cpp -o amath583.oamath583.o : amath583.cpp amath583.hpp Vector.hppc++ -I/usr/include/python2.7 -c amath583.cpp -o amath583.o -lpython2.7amath583.o : amath583.cpp amath583.hpp Vector.hpp$(CXX) $(CXXFLAGS) -c amath583.cpp -o amath583.o$ make clean2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 6/21This is a rule defined at the bottom of the Makefile and deletes all of the generated filesin your project (.o and .exe files) as well as other detritus that might have appearedduring the compilation and editing process.Now, issue the commandThis will process the rules for building julia.exe but since we are passing the -n optionto make important make will print out what would be done, without actually doingthose things.You should see something likeIf you look at the Makefile you will see thes linesThese define the macros CXX , OPTS , etc. Note that CXXFLAGS is defined in terms ofthree other macros. The convention we will be using in this course is to separatelydefine different classes of flags that we might pass to the c++ compiler and thenbundle them all together into the CXXFLAGS macro. We use OPTS for setting optimizationlevel (and debugging level), LANG to set the C++ language level, and PICKY to set howpicky we want the compiler to be when processing our code. The options here indicateto use no optimization, c++11 as the language level, and to use maximum pickinesswhen compiling.$ make -n julia.exec++ -std=c++11 -g -O0 -Wall -c julia.cpp -o julia.oc++ -std=c++11 -g -O0 -Wall -c amath583.cpp -o amath583.oc++ -std=c++11 -g -O0 -Wall julia.o -o julia.exeCXX := c++OPTS := -g -O0LANG := -std=c++11PICKY := -WallCXXFLAGS := $(LANG) $(OPTS) $(PICKY)2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 7/21Do you recognize the values of each of these macros in the text that was printed whenyou invoked make -n julia.exe?To see how the macros work, make a temporary change to the Makefile by changingLANG to beInvoke make -n julia.exe again. Is there a difference between what was printed the firsttime and what was printed now?Be aware that the macro Processing is simple text processing, it has no actualmeaning relative to what flags the compiler actually supports or what the compilationprocess actually is. We choose CXX and LANG and so forth as aids for our owncomprehension of what we are trying to accomplish. For example, you could put aninvalid flag into a macro and make would still invoke the command and you wouldsee the resulting error from the compiler when it is invoked.Edit your Makefile again, this time adding a nonsense string to LANG e.g.,make -n julia.exemake julia.exemake -k julia.exe ImportantWe didnt discuss what make would do in the case of errors. In the default case, if itis unable to build a target due to some error, it will halt and not build any othertargets. If you pass the -k option, it will continue past the error and attempt to buildas many targets as it can.Lastly. If you look at the lines in the Makefile, there is still alot of repetition. Notrepetition in the exact text, but repetition in the following sense. For the rules that build.o files, there is a rule for the .o, the corresponding .cpp dependency and a compilationLANG := -std=c++17LANG := -std=c++17 asdfasdfasdfWhat happens when you invoke2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 8/21step to turn that .cpp into a .o.Every time you see repetition you should be thinking about how to create rules andprocess so that the repetitions can be made by the computer rather than you. In afuture assignment we will look at how these kinds of patterns can also be handled bymake .4.3 Defensive Programming and AssertionsMaurice Wilkes was one of the founders of modern computing and, in some sense, ofdebugging. One of his most poignant quotes is:It was on one of my journeys between the EDSAC room and the punchingequipment that hesitating at the angles of stairs the realization came over me withfull force that a good part of the remainder of my life was going to be spent infinding errors in my own programs.Over the years, defensive programming has evolved as a set of techniques that can beused to help you find your own errors. One fundamental part of the process ofdefensive programming is to develop your program so that it supports two differentmodes of compilation and execution: debug mode and release mode. In debug mode,a program is first of all, compiled to enable use of a symbolic debugger (using the -gflag to the compiler). In addition, the program itself includes self-checks, or assertions,(inserted by the programmer) to insure that necessary program invariants hold.4.3.1 AssertionsNote that these self-checks (assertions) are not the same as error-checking.Assertions are there to catch mistakes that you make while programming, whichmistakes would result in erroneous behavior and/or catastrophic failure of yourprogram. Error-checking catches mistakes that the user of your program makes and ispart of normal program logic for a correctly functioning program. Incorrect logic (akabugs) are errors that are not part of normal program logic and are what we want to tryto prevent with assertions. Importantly, assertions are removed (automatically) from therelease mode of the program, whereas error-checking is always enabled.Correct program logic depends on invariants holding during the course of execution.During development and debugging it can be useful to check these invariants and toterminate the program at the point where an invariant is violated. C and C++ provide achecking facility for asserting such invariants in the cassert header.There is a concise description of the principles of using assert here: https://bit.ly/2o9THxq . Exactly how and where to use assert when you areprogramming will largely be up to you, but you should add it to your arsenal of tools2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 9/21and techniques for programming in this course (and beyond) so that the remainder ofyour life can be spent doing more interesting things things than finding errors in yourown programs.An assertion statement will print a message and cause a program to halt if theassertion fails, that is, if the expression passed to it evaluates to false or, equivalently,to zero (false and zero are essentially the same value in C/C++). As mentioned above,assert statements are removed from your program for its release mode. This removalis done functionally rather than physically – you dont actually go through the code andremove the assert statements. Rather, they are turned into empty statements in apreprocessing step by the compiler if the macro NDEBUG exists in the environment priorto inclusion of the header file cassert . Try the following three programs (assert0.exe,assert1.exe, and assert2.exe in your Makefile).#include iostream#include cassertusing namespace std;int main() {assert(1 == 1 This is true); // will not be triggeredassert(1 == 0 This is never true); // will be triggeredcout Hello World endl;return 0;}#define NDEBUG#include iostream#include cassertusing namespace std;int main() {assert(1 == 0 This is never true); // will be triggeredcout Hello World endl;return 0;}2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 10/21Which version prints Hello World?The technique of using the logical and operation () in addition to a string lets youinclude a helpful message when the assertion line is printed when there is a failure.The string is not necessary: assert(1==0) would be sufficient to trigger a failedassertion. NoteWhat you pass to assert is something you expect to always be true for correctoperation of the program and, again, is a check that will be removed for the releasemode of your program. For example in the sqrt example we have been using inlecture you might include an assertion that the input value is non-negative:4.3.2 -DNDEBUG#include iostream#include cassertusing namespace std;#define NDEBUGint main() {assert(1 == 0 This is never true); // will be triggeredcout Hello World endl;return 0;}double sqrt583(const double y) {assert(y = 0);double x = 0.0, dx;do {dx = – (x*x-y) / (2.0*x);x += dx;} while (abs(dx) 1.e-9);return x;}2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 11/21Making sure the assertions are removed is an important distinction between debug andrelease modes of a program. We have seen how they can be elided with the use of theNDEBUG macro. But if we think about how we would switch between debug and releasemode in this way we would be (manually) inserting and remove NDEBUG from all of ourfiles every time we changed modes. And we are sure to make mistakes (not to mentionwaste time) in doing so. At this point you should be thinking hmm, doing somethingboring and repetitive by hand there must be a way to automate that. And in factthere is. One can pass macros to the C++ compiler from the command line using the-D flag. I.e., to define NDEBUG , we add -DNDEBUG to the set of flags we pass to thecompiler. And we already know how to do that in an automatic and repeatable fashion:add it to a macro that ends up in CXXFLAGS . We will use OPTS for that in this course.(In general, avoiding work for the sake of avoiding work is called laziness and is notconsidered to be a virtue. However, in the context of programming, we are avoidingboring and repetitive and mindless work so that we can instead focus our energy oninteresting and challenging tasks. This kind of laziness is a virtue. It also sometimesleads one not to just use tools to save time but to develop altogether new tools. Inthis case you might end up spending more time developing your time saving tool thanthe time you actually save. Moderation is also a virtue.)4.3.3 Compiler PickinessSince a compiler is built to translate a program written in a given program language, itcan also be used to analyze how programs are written. Both clang (llvm) and g++ usethe flag -Wall to enable pickiness, meaning the compiler will issue warnings for justabout anything in your program that might be suspect. Warnings are not fatal, yourprogram will still compile and run if warnings are issued. But, as part of defensiveprogramming, your programs should always compile cleanly with -Wall enabled. Formaximal pickiness you can additionally use -Wextra and -pedantic . ImportantYour code should always compile cleanly with -Wall enabled. No warnings and noerrors.4.3.4 Language Level SupportThe C++ programming language is still being actively extended and improved upon bythe ISO standards committee responsible for it. There are four versions of thelanguage that represent major milestones in the evolution of the language: C++98,C++11, C++14, C++17. And the fifth was recently approved: C++20. (The committee istargeting a new release every three years at least through C++26.)2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 12/21Although standards are developed (and named) by the standards committee, it doestake some time for compilers as well as programs themselves to catch up to thestandards. Although it is currently 2021, the default level of language support for clangand g++ is still C++98. This is a reflection more that the vast majority of extant C++code is written in C++98 than it is a reflection of the timeliness of the compiler writers.To specify a given level of language support (to enable certain features that are in onethat are not in an earlier one), we can pass one of the following flags to the compiler: -std=c++11, -std=c++14, -std=c++17, or even -std=c++20. Since C++20 is stillfairly new, you should not expect it to be fully supported at this time (but neither will youneed to use many of its features, if any at all).For this course you are welcome to use any level of the C++ language that you like, aslong as it is at least C++11.5 ExercisesIn this assignment we will be using a combination of specified test scripts and testingcode to verify behavior of your programs. Your programs will be graded against theexpected behavior with the tests that your are provided, as well as with additional teststhat only the TAs will apply.The test script for this assignment is verify.bash . It will run through a set of tests foreach of the exercises below, indicating whether the program has passed or failed thatparticular test. For most of the executables that you will be asked to write, the script willattempt to build the executable using the make command and then to run theprogram.You can run the test script by invokingSome of the programs that will be build are themselves testing programs that willexercise different aspects of the functions that you will be asked to write. Partial creditwill be given in these cases for the parts of the program that do pass their internaltests, even if the executable itself does not pass as a whole. We will discuss programtesting in future assignments.5.1 AssertionsTo-Do 1: In your subdirectory there is also a file assert3.cpp that has the sameassertions as assert1.cpp and assert2.cpp but without NDEBUG being defined in theprogram. Modify the rule for compiling assert3.exe do not modify assert3.cpp so$ bash verify.bash2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 13/21that the assertion in assert3.exe will not be triggered. NoteAs a reminder this contrived example is to show the behavior of assert() andNDEBUG. In practice, we dont insert NDEBUG so that failing assertions will nolonger fail. We insert NDEBUG so that the function call overhead of calling theassert() function will not be present once all assertions pass.5.2 Hello World!Write a new hello world program put it in a file called hello_world.cpp. Rather thansaying hello to the world, I want you to simply print out a number indicating how faraway you are from Lewis Hall when you did this assignment (in kilometers). You dontneed to compute anything (or even be exactly correct, you wont be graded on whatthe number is) you can just write the number directly in the file and print it (either as anumber or as a string). We will collect the output from these programs to test theleaderboard feature of our autograder.5.3 ZeroizeIn the file amath583.cpp are five functions, three of which you need to complete andtwo of which are already written as examples. You will also need to add some functionsfrom scratch. Every function that is defined in amath583.cpp also needs to be declaredin amath583.hpp.Deliverable 1: Complete the definition and declaration of zeroize() in amath583.hppand amath583.cpp. This function should take a Vector as an argument and fill eachentry of the Vector with a zero.This function will be tested by linking amath583.o against test_zeroize.o to createtest_zeroize.exe .5.4 Vector NormThe file amath583.cpp contains an implementation of one_norm as followsdouble one_norm(const Vector x) {double sum = 0.0;for (size_t i = 0; i x.num_rows(); ++i) {sum += std::abs(x(i));}return sum;}2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 14/21The corresponding declaration in amath583.hpp is:Deliverable 2: Complete the bodies of two_norm() and inf_norm() which respectivelycompute and return the two norm and infinity norm of the Vector that is passed in as aparameter.These functions will be tested by linking them with test_norms.o which contains aseries of unit tests that check different expected behavior of the norm computations.5.5 Inner ProductDeliverable 3: Add a function called dot to amath583.cpp and amath583.hpp(definitions and declaration). The function should take two vectors as arguments andreturn their inner product (the sum of the pairwise products of each correspondingentry in the vectors).The tests for this function are in test_dot.cpp , which should be compiled as with theother test programs into test_dot.exe .Question.1. How would you use dot to implement two_norm ?5.5.1 Extra credit (483 only)Deliverable 4: Implement a function two_norm_d() using dot() .The tests for this function are in test_norm_d.cpp , which should be compiled as with theother test programs into test_norm_d.exe .5.6 Matrix NormIf we consider a typical vector space of N-tuples, e.g., , the set of all linearoperators mapping to (say) is the set of all matrices. But, if we thinkabout the kinds of things we can do with a matrix we can add them, scale them, etc all the things we can do with objects of a vector space. And, in fact, matricesover a field, form a vector space. If the field is the real numbers, we write .double one_norm(const Vector x);RNRN RM M NM NRMN2021/4/14 Problem Set #2 AMATH 483/583 High-Performance Scientific Computing httpss://amath583.github.io/sp21/assignments/ps2.html 15/21Just as with other kinds of vectors, it is useful to define a norm over matrices. Onesimple option would be to just unravel the matrix into an vector and use oneof our vector norms. That would be a norm for the matrix in some sense, but in linearalgebra we are often more interested in how a matrix behaves as an operator and wewould like for matrix norm to capture something about the operator-ness of the matrix.This kind of norm is called an induced norm and is defined as follows.If is a norm on any n-dimensional vector space, e.g., , then the induced matrixnorm of a matrix is given byFor the one norm we then haveAnd for the infinity norm we haveThe vector norms we looked at earlier are specific cases of -norms, defined asWhile it is straightforward to compute these for vectors using addition, subtraction,multiplication, etc., the only directly computable (meaning computable in a fixednu”
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
