Thursday, March 5, 2015

Conference Attendance SIGCSE 2015 - Day 1 Morning

It is colder here in Kansas City.  Fortunately, I will only be outside briefly.  Most often I will be networking and continuing my efforts to both become a better teacher, as well as finding an academic job teaching.

This morning, I am focusing on the "Curriculum" track.  I am excited by the three papers in this track, the first looks at research, the second is on systems courses, and the last on parallel computing courses.  Alas, I was in the hallway track and missed the first work.  Perhaps I can find the authors later.

Backward Design: An Integrated Approach to a Systems Curriculum
The goal of systems is "higher level software creation".  Computer Science courses are split into Core Tier 1 and Tier 2 (a term from the ACM 2013 curriculum), where the former are taken by all CS majors and the later are only taken by most or some.  One issue in the old curriculum was that OS also taught C.  In crafting a new curriculum, first establish a vision statement, which can be used in conflict resolution (and also revised).  Establish SMART objectives to prepare and build the assessments.  The results can be found on github.

A Module-based Approach to Adopting the 2013 ACM Curricular Recommendations on Parallel Computing
Parallel computing is important and important for CS graduates to know.  The 2013 ACM Curriculum increased the number of hours that students should take in parallel computing.  Part of the recommendations are to place parallel computing into the curriculum and not just as a course.  Thus parallelism modules are placed throughout the curriculum (perhaps as early as CS1 or CS2).  Find the level of abstraction for a concept and introduce it appropriately.  For example, Amdahl's Law in CS1 versus cache coherence in senior-level class.  5 modules of parallelism were established, which have equivalences with the ACM.  Each course in the curriculum may have 1 or more modules, which then teaches and reinforces the topics.  Even after adding these modules, there has continued to be incremental development and revisions, which have improved student outcomes.  The key take away is that it is possible to introduce these recommendations without completely rewriting the curriculum.

In the afternoon, I will be standing with my poster -  Using Active Learning Techniques in Mixed Undergraduate / Graduate Courses.  Later I will post updates from my afternoon.

Monday, February 23, 2015

Compilers and Optimizations, should you care?

Compiler optimizations matter.  One time in helping a fellow Ph.D. student improve a simulator's performance, I did two things: first, I replaced an expensive data structure with a more efficient one.  Second, I turned on compiler optimizations.  Together, the simulator ran 100x faster.

A question posted in the stackexchange system asked, "Why are there so few C compilers?"  The main answer pointed out that any C compiler needs to be optimizing.  Lots of optimizations are occurring on every compilation, and each one gaining tiniest increments in performance.  While I enjoy discussing them in detail, I generally wave my hands and tell of how they are good, yet make debugging difficult.  These optimizations are lumped together as the "optimization level".

In "What Every Programmer Should Know About Compiler Optimizations", we revisit optimizations.  First, the compiler is no panacea and cannot correct for inefficient algorithms or poor data structure choices (although I am party to a research on the later).  The article then suggests four points to assist the compiler in its efforts at optimizing the code. 

"Write understandable, maintainable code."  Please do this!  Usually, the expensive resource is the programmer.  So the first optimization step is to improve the programmer's efficiency with the source code.  Remember Review: Performance Anti-patterns and do not start optimizing the code until you know what is slow.

"Use compiler directives."  Scary.  Excepting the inline directive, I have used these less than a half dozen times in almost as many years of performance work.  Furthermore, the example of changing the calling convention is less relevant in 64-bit space where most conventions have been made irrelevant.

"Use compiler-intrinsic functions."  (see Compiler Intrinsics the Secret Sauce)  This can often dovetail with the first point by removing ugly bit twiddling code and putting in clean function calls.

"Use profile-guided optimization (PGO)."  This optimization is based on the dynamic behavior of the program.  Meaning that if you take a profile of the program doing X, and later the program does Y; executing Y can be slower.  The key is picking good, representative examples of the program's execution.

So you have dialed up the optimization level, and written understandable code sprinkled with intrinsics.  Now what?  The next step (with which I agree) is to use link time optimizations (LTO) / Link-Time Code Generation (LTCG).  This flag delays many optimizations until the entire program is available to be linked.  One of the principles of software performance is that the more of the program available to be optimized, the better it can be optimized.  (This principle also applies in computer architecture).  Thus, by delaying many optimization until the entire program is available, the linker can find additional and better opportunities than were present in individual components.

The article notes, "The only reason not to use LTCG is when you want to distribute the resulting object and library files."  And alas, I have fought several battles to overcome this point, as my work requires the use of LTO.  Perhaps in the next decade, LTO will be standard.

Wednesday, February 18, 2015

Going ARM (in a box)

ARM, that exciting architecture, is ever more available for home development.  At first, I was intrigued by the low price points of a Raspberry Pi.  And I have one, yet I felt the difficulties of three things: the ARMv6 ISA, the single core, and 512MB of RAM.  For my purposes, NVIDIA's development board served far better.  At present, that board is no longer available on Amazon; however, I have heard rumors of a 64-bit design being released soon.

With the release of the Raspberry Pi 2, many of my concerns have been allayed.  I am also intrigued by the possibility it offers of running Windows 10.

Monday, December 8, 2014

Improving Computer Science Education

Recently in the news are two articles that relate to improving Computer Science Education.  It is valuable to broaden the base of students who understand the basics of computing, just as students are expected to know Chemistry or Calculus.  In fact in my biased opinion, knowing the basics of computing and programming will have greater practical benefit to students; however, it should never be at the expense of a diverse education.

The White House announced that the 7 largest school districts will be including Computer Science in their curriculum.  This will quickly lead to another problem of who will teach the Computer Science classes.  Not me, but I am interested in teaching the teachers.  I do want to see Computer Science as an actual specialty (endorsement) for Education majors.

Another aspect of broadening the base is retaining students enrolled in the major.  Being part of the majority, it is difficult for me to know the challenges faced by other groups.  Similarly, I know why I entered Computer Science, so I would like to understand why others have too.  Why are they passionate or interested in this field that I am a part of?  Here are some things minority students have to say about STEM.

Wednesday, November 26, 2014

Computer Science Diversity

I attended a top program in Computer Science, where the gender split was 60 / 40.  Then I worked for five years at a major company.  Therefore, my expectation is always that anyone regardless of their gender, race, etc can succeed in Computer Science.  Now, recently there was a short lived Barbie book about being a computer engineer.  Ignoring any semantics about Computer Science, Software Engineering, and Computer Engineering being different disciplines, the work still did not portray women in the more technical efforts.  I'd rather read a collegue's remix of the work.

In a different vein of diversity, as a white male, I have been regularly been excluded from tech events because I dislike the taste of alcohol.  Thus at the (especially) frequent events in industry settings where alcohol is served, I was not socializing with my colleagues, and instead would inevitably find myself back at my desk working.  As a consequence, I was effectively excluded from the event.  And now in academia, I find myself attending conferences, where the social events are also touted for serving alcohol.  I have no issue with serving alcohol, rather it is the near exclusivity of which the drink options trend that way.  Thus a recent article struck a chord in the continuing desirability of extending the options and respecting the decision (for whatever reason) to not drink alcohol.

Monday, October 27, 2014

Liberal Arts College Positions Mini-Seminar

In continuing my search and preparation for a faculty position, today I attended a mini-seminar by LADO faculty.  (LADO - liberal arts colleges with diversity officers)  Here are some points that were raised during the breakout and panel discussions:

Teaching:
- You will teach both upper-level courses, as well as "service" courses.  Service is a good term to describe the low-level / introductory courses, as the faculty are rotating through this service to the department.
- Try to setup the teaching schedule so that 1 day is free solely from research.
- Continue to revise courses so they are fresh and current, but also avoid constantly creating all new courses.
- Valuable to set aside "non-office hours" times, during which the door can be shut.
- Faculty will sit in on courses and additionally interview the students, as part of composing an evaluation of your teaching.

Research:
- Recruiting undergraduates earlier for research to have time to train them, so that they will later be able to contribute.
- You can still collaborate and have broad impact through research with faculty at other more research-focused institutions.
- Grant proposals can also be keyed "RUI" (research at undergraduate institutions)
- Regular funding for sabbatical leaves, first often after the renewal of the 3-year contract.  This leave is focused on research and may be held at R1 or other institutions.
- Startup package is present to cover the transition to grant-based funding.
- Research lab costs are significantly lower at these institutions, as funds are not required for grad students, post docs, etc.
- Schools are looking for faculty hires that add diversity to the research available.

Service:
- Service is a component, but is much smaller than teaching and scholarship.  So be cautious about accepting invitations to committees, in terms of time commitment.  The service time can provide valuable insight to the functioning of the institution, as well as possible collaboration with collegues in other departments.
- You will be chair of your department someday.

Other:
- Many liberal arts institutions are located in small towns.
- Take the time to customize the cover letter.  Do you really want and care about this job?

Wednesday, October 15, 2014

Richard Lipton - Knuth Prize (Practice) Talk

Richard J. Lipton is the 2014 winner of the Knuth Prize.  His talk today was a summary of his work, which lead to received the prize.  The talk proved to be a series of short anecdotes, which are difficult to capture, but I've copied down the highlights, as best as I can.

"Do problems have labels?"  For example, simulate a queue as two stacks, is this a theory problem or system problem?  At the time, the qualifying exams were split by problem types, so labeling it mattered for which exam contained it.  Faculty at Yale were 50/50 split on whether to mix the problem types and instead students would sit for several days of CS questions rather than a theory day, then a systems day, etc.

Finding a division, separator to a planar graph, in root time.  T(n) <= C*T(n/2)
In explaining the result to Knuth, while visiting Tarjan, who responded "You've ruined my lunch."  As the result destroyed the best known algorithms that were being written, at the time, in Vol. 4.

"Throw away comments are wrong"  Many introductions make inaccurate statements like "non-uniform cannot imply uniform".  There is the work of Karp-Lipton dealing with non-uniform circuits and the uniform nature of algorithms.  The proof was later handed out on tote-bags at CCC 2010.

"Think in High Dimensions"  Binary search in high dimensional space, still logarithmic in the number of elements.  For example, take a planar graph and split it by the intersections, each slab is linear and can be quickly searched.

"Learn New Tools"  Now, one tool is "Probabilistic method" published on June 28, 1974, which shortly thereafter was a Yale seminar.  "By an Elementary Calculation" means to Erdos to use Sterling's approximation, which in one case required taking the approximation to 7 places.  Before learning this method, had been asked about the problem of Extendible Hashing, and had no idea and put it out of mind.  Later asked about it again, and the problem solved easily (or perhaps two days of proofs).

"Guess Right" One problem in solving problems in the community is that we are guessing wrong.  "It is really hard to prove false statements."  Take the problem of detecting whether a sequence of a_nb_m has n = m?  Possible using a multi-pass scan with a probablistic FSM.  Can do with one-way (i.e., single pass)?

"Need a Trick" Solving a problem of vector addition, with fixed counters, with adding and subtracting (where cannot subtract from 0).  1 counter is decidable, 2 counters is not.  But if there is no test for whether the counter is 0.  Proved it takes EXPSPACE-hard.  Pair counters, so add is subtract and vice versa.

"My Favorite Two Results" - Proving that a a^-1 = 1, in long sequence (abaaaba^-1...) can be done in LOGSPACE.  Do so by replacing the a, b with matrices, then modulo prime.  Given the distributed law and applying in any order, prove that it always stops on any expression.

"Future" Old problems, yes.  But dream of finding proofs to math problems that use CS theory tricks.