Thursday, August 28, 2014

0397 Longest monotonically increasing subsequence

Given a random sequence, find the longest subsequence such that all subsequence elements are in monotonically increasing order.

Example, given sequence {7,8,9,1,2,3,6}, longest increasing sequence (LIS) is {1,2,3,6}.

I come across this classical problem while reading Dynamic Programming chapter in CLRS algorithm book. Given the dynamic programming context, trying dynamic programming becomes my first thought.

Wednesday, August 27, 2014

Configuring a new internal hard drive with docking station

This was frustrating. I bought a hard drive docking station from amazon and a 3TB hard drive from Rakuten lately with high expectation that I finally find a place to put my messy documents and archives. Both arrived today in one piece. So I thought it should be frustration-free to hook those up to my laptop. It turns out to be a nightmare (for newbies like me).

With the out-of-factory hard drive plugged in and usb docking station connected, I was 'surprised' to find out the new hard drive has 'not been recognized' by the laptop. I see device activated with a nice beeping sound from my laptop indicating new hardware connected, and the new hard drive starts its engine, But, no new volume shows up, no autoplay starts. This error could comes from any of those three devices:
  1. Defected hard drive;
  2. Docking station needs a driver or broken;
  3. My laptop.
Tuning the hard drive itself would be hard since I do not have a spare hard drive at hand. I tried to disassemble my other external hard drive but its screwless design stopped me from destroying it.

As to the docking station, my laptop displays chipset ASM1053E. A driver for this chipset is not needed as far as I know.

Besides, I can hear the hard drive spins happily and all lights on (it would be great if they are blinky). I don't think I'm that bad luck to get a defected hard drive. Time to fix my laptop.

What can I think of? 

  1. USB 3.0 controller driver issue;
  2. Disk driver issue;
  3. BIOS or MB issue (No one want this to happen)
That's about it. I am using an Intel 7 series usb host controller. Users on the forums had posted issues about usb 3.0 connection but none looks like mine. An update from official forum suggests a driver update since my old driver is already 2.5 years old. I did not uninstall my old driver in case doing so will cause unexpected issues. Luckily during the new driver installation most old files have been overwritten. A reboot is required. But unfortunately this does not solve my problem.

Disk driver issue? Let's check DISKPART.  


Actually the above images are not what I got. Diskpart crashed before me when I tried to access disk info. By then I suddenly realized what DISKPART is trying to tell me. I can detect the existence of this new hard drive, but cannot read any partition info from it. What is the problem? Broken file system? I don't even have one! Yes, A disk partition is needed before I use any internal disk. Just like what we did during system installation.

The remaining part is simple once I am finally on the right track. With the help of dskmgr.exe, partitions were built and disk shows up correctly in my explorer now. Hooray.

It was not fun to play until 4am, right?

Thursday, October 31, 2013

A simple cache simulator project

Cache simulator fun — CodeChat template version 0.0 documentation

Cache simulator fun

The task in this homework is to write a simple cache simulator. Your program has the following requirements.

Input File Format

Your program must be able to parse memory trace files that are in the Dinero text format (Dinero is a well‐known cache simulator). This is a simple text format that is given below:
2 20d  Dinero input format "din" is an ASCII file with
2 211  one LABEL and one ADDRESS per line. The rest of
0 1fc780  the line is ignored so that it can be used for
1 7fffccb0  comments.
2 213
2 217  LABEL = 0  read data
0 1fc77c   1  write data
1 7fffccac   2  instruction fetch
2 219   3  escape record (treated as unknown access type)
2 21d   4  escape record (causes cache flush)
0 1fc778
1 7fffcca8  0 <= ADDRESS <= ffffffff where the hexadecimal addresses
2 21f  are NOT preceded by "0x."
2 223
2 220
You will be provided with a couple of memory trace files in this format along with ‘golden’ results from several sample runs. In the above format, ‘read data’ and ‘instruction fetch’ both count as ‘read accesses’. You are to simulate a unified cache, which means instruction and data are both stored in the same cache.

Program Options, Program output

You program must be able to be run from the command line and support the following command line format:
Program_name infile <options>
Valid options are:
<-l1-usize num_bytes> : total size in bytes
<-l1-ubsize num_bytes> : block size in bytes
<-l1-uassoc num_levels> : associativity level
<-l1-urepl type> : replacement policy, 'l' - LRU, 'f' - FIFO
<-l1-uwalloc type> : write allocation policy, 'a' - always, 'n'-never
These options are compatible with the DineroIV cache simulator. Sample command line runs are shown below (the program name is cache_sim, and the input file is tex.din):
cache_sim tex.din -l1-usize 1024 -l1-ubsize 32 -l1-uassoc 32 -l1-urepl f -l1-uwalloc n
cache_sim tex.din -l1-usize 1024 -l1-ubsize 32 -l1-uassoc 4 -l1-urepl l -l1-uwalloc a
cache_sim tex.din -l1-usize 1024 -l1-ubsize 32 -l1-uassoc 1 -l1-urepl l -l1-uwalloc a
Your program must output the number of cache misses for the given options and input file. Sample output is shown below. The only important information in the output is the line ‘Demand Misses 42825’ – your output must contain a line like this, in this exact format as my regression script parses the output and looks for a line that starts with ‘Demand Misses’
cache_sim tex.din -l1-usize 1024 -l1-ubsize 32 -l1-uassoc 4 -l1-urepl l -l1-uwalloc a
Running with l1-usize=1024, l1-ubsize=32, l1-assoc=4, l1-repl=l, l1-uwalloc=a
Number of cache lines is: 8
Demand Accesses 832477
Demand Misses 42825

What you are provided

The ZIP archive for this homework contains the following:
  • traces/ folder – contains three trace files that can be used for testing.
  • cache_sim.exe - Windows x86 executable that is my solution to this problem. This can be used to obtain sample results
  • goldAll_espresso.log, goldAll_tex.log - correct output for several runs using the trace files espresso.din, tex.din. Dr. Reese reserve the right to test your program with more than these options.
  • cache_sim.py - Skeleton files that have parsing of the required command line arguments in Python. You can use these as starting points if you desire.
  • regress.check.py - A regression test script that takes three arguments: the name of a golden cache simulation executable (i.e., ‘cache_sim.exe’), the name of your cache simulation executable, and the name of a trace file. It will run both programs on the trace file using several options, compare the results, and report failures.

Implementation

Skipped

Indices and tables