You are currently browsing the FeradZ Blog blog archives for January, 2009


Windows XP – Microphone not Working

Today I had to fix an annoying microphone problem on my brother’s computer. He has Windows XP Professional installed and the microphone was not working – unable to use the microphone in any application. The solution to this problem is very subtle since you have to enable "MIC boost" a very hidden feature. Here is how to do it:

Open the extended Version of Volume Control (down right next to the clock, right click and select properties).

You have to see the following picture:

In Volume Control dialog:

  1. Ensure that Muted is checked for microphone (if not you will be able to hear yourself on the speakers when talking to the microphone)
  2. Then click Advanced for Microphone and select "MIC boost"

Then Close everything and now your microphone should work properly.

Sorry that the first image is in Bulgarian. I will change it as soon as possible.

Configuring Yoigo Mobile Internet Connection in Sony Ericsson

This article describes how to setup your Sony Ericsson mobile phone so that to be able to connect to Internet with your mobile phone over Yoigo mobile operator in Spain.

The configuration consists of two but small steps:

  1. Setup data account. If you bought your phone from Yoigo this step is done by the operator so you will not need to do it.
  2. Create internet profile.

Setup Data Account

If you bought your phone from Yoigo this step is done by the operator so you will not need to do it. If you don’t have a configured data account continue with the following steps.

  1. From the menu of your phone go to Settings->Connectivity->Data comm.->Data accounts->New Account
  2. Account Type = PS data and continue with select
  3. Name -> Name the data account could be anything, for example "Yoigo Net" and continue
  4. APN = Internet
  5. Username = leave empty
  6. Password = leave empty
  7. Login request = off
  8. Allow calls = automatic
  9. IP address = … (type 3 dots)
  10. DNS address = … (type 3 dots)
  11. Authentication: select "None", "PAP" and "CHAP"
  12. Data compression = off
  13. Header compression = off
  14. From the menu of your phone go to Settings->Connectivity->Data comm.->Preferred service and select "PS and CS"

Create Internet Profile

To create and internet profile first ensure that you have the data account. Then continue with the following steps:

  1. From the menu of your phone go to Settings->Connectivity->Internet settings->Internet Profiles->New Profile
  2. Name = any name is OK, for example "Yoigo Net Prof"
  3. Connect using. Here you have to select the data account to be used to carry to network communication. Assuming that you named your data account "Yoigo Net" (see Setup Data Account) select "Yoigo Net"
  4. Then select the internet profile you have just created "Yoigo Net Prof", select More from the menu and choose Settings
  5. Use Proxy = yes
  6. Proxy address = 010.008.000.036
  7. Port = 8080

After completing these steps you should be able to connect to the internet with your mobile phone using the integrated mobile browser.

Is Linux Easy to Use?

This morning while we were drinking coffee with my home mate Cristian, we had a small discussion if Linux is easy to use? I and my friends have many times been talking about that and this time the topic opened again because yesterday I bought a new Eee PC 901 Linux laptop and its wireless didn’t work out of the box. Our conclusion at the end of the coffee was that Linux made great step ahead. Today it is very user friendly, intuitive and easy to use – particularly the Ubuntu distribution, than it was before 10 years. But it is not as friendly as Windows or Mac OS are. Because this article may make many enthusiastic Linux users angry, I would like to say in advance that it is not “Linux is bad and other operating systems are good” kind of writing, at all.

I use Linux for long time probably 10+ years. It is very powerful, reliable and stable operating system (this does not imply that the other OSs are not). But I think that it is difficult to use by people with little knowledge about computers such as my brother and mother are for example. Sooner or later, a Linux user will need to edit some configuration file, or script, do something on the terminal or even probably compile some library, module or application. There isn’t anything wrong with that if the user is computer science student for example. But this horrifies the common user – the common user does want everything to be intuitive, automatic and with minimal options.

I think that the difficulty of using Linux is not in the GUI but the configuration and setup of the system. I find the GUI (KDE and Genome) is rich and intuitive enough. But the problem is for example when you just install the system and some driver is missing or bought a new non-standard hardware. Then you can spend days to make it running.

What are the Current Problems?

I identify three points that make Linux difficult to use or less preferable (not ordered by importance):

  1. Unsupported device drivers
  2. Software management and library dependencies
  3. Not sufficient commercial quality software

Unsupported Device Drivers

Many hardware companies do not develop Linux drivers for their devices. What happens is let’s say a volunteer developer tries to implement these drivers manually by revers engineering those available for other operating systems. These drivers then cause the device to not function properly and frustrate the end user because of poor experience. This problem was much more evident before but today when most of the interfaces are standard is less important, but it still exists. For example, it took me few days to make my web cam running in Linux, or the microphone working with the messaging applications (these are not relevant to the EEE PC, there everything worked out of the box). A common user wouldn’t cope up with these problems as it required me to search on the web, write on forums and read posts, compile kernel modules and modify scripts to load these modules at start up. In the earlier distributions of Kubuntu I had a problem with suspend and resume – a small but frustrating problem.

Software Management and Library Dependencies

Linux is open source and the complete system (not just the kernel) comprises of thousands of open source libraries and programs. Open source is something great – it is not just sharing but a philosophy. Everybody can develop an application or a library. Then somebody else takes it, and implements a program which extends the features of the previous library or builds on top of it. But this creates the problem of the dependency – my program depends on the interface of a specific version of a certain library. So if you want to install my program you have to find the exact version of the library that my application depends on. But what if another program depends on a different version of the same library. We have a conflict. Of course, the example I gave here is idealized and much simplified than it is in reality. This problem was very serious before. The Advanced Packaging Tool  (APT) first introduced with Debian (it might be possible that apt tool originates from other distro that I don’t know) brought a light to this mess. But again the problems exist but this time termed as broken package. For example, when I installed my Kubuntu 8.10 Intrepid my standard wireless didn’t work with the WPA encrypted network. The problem was in the knetworkmanager. It took me a week to fix it because I was one of the first experiencing the problem and yet there wasn’t an existing solution. Other problem I have is playing back the video files – a problem caused due to a bug in the XVideo and beryl/compiz better described at "Video playback problems (black) after installing Beryl (or Compiz)" (ok this is not much relevant with broken package).

Not Sufficient Commercial Quality Software

I think that there is much less commercial quality software targeted for general home or office end users for Linux than for Windows or Mac. Let me clarify my classification of "software targeted for general home or office end users" by giving example applications that fall in this category:

  • Multimedia editing and organization – particularly video editing.
  • Games.
  • Office – I find Open Office to be pretty good for home use but not office where time costs money.
  • Image editing – Gimp is powerful but hunting for plug-ins and installing plug-ins is not for general users.
  • And other that I cannot recall but would add later.

However there is very good commercial quality open source special purpose or domain specific software for Linux. Examples are gcc, Firefox, Emacs, Apache, I do think Open Office and Gimp are good, may libraries such as glibc and STL and many other that I cannot list here.

What Improved in Linux?

We also talked about what improved in Linux for the past 10 years let’s say:

  • Easy installation.
  • More intuitive and rich GUI.
  • More software for home and office use was developed.
  • More supported device drivers.

Easy Installation

Today’s Linux distributions such as Ubuntu, Suse and Fedora can be installed very easily. In Ubuntu the user required actions are just 4-5 clicks. The installer is clever enough to partition the hard disc without loss of data and co-living with other operating systems installed prior. I love this feature a lot.

More Intuitive and Rich GUI

KDE4/Genome combined with a compositing window manager such as compiz/beryl make the user experience exceptional. These fancy desktops are what the end users want – including me :).

More Home and Office Software

  • Codecs and applications for playing video appeared such as kaffeine, Mplayer, and Totem, xmms appeared.
  • Applications for organizing photos such as Picasa and digiKam.
  • Word processing – Open Office.
  • Internet – Firefox, Thunderbird, Evolution.
  • Games – I am not a game fan and don’t know which popular games are available on Linux but I heard this from my friends.

All these improvements made Linux attractive for home and office end users. That’s why some computer manufacturers considered to ship some of their PCs with preinstalled Linux distribution thus decreasing the market price of the product. Once you have your Linux distribution configured, setup and running one can be happy with it. So refining my answer of the question "Is Linux easy to use?" would be more correct to say "It is easy to use Linux, but difficult to configure and set it up.". And now another question may arise – "Where is the boundary of using and configuring?".

References

Here are some references relevant to this article.

 

Cache Efficient Matrix Multiplication

In this article I will show a cache efficient algorithm for matrix multiplication and the impact of caches on the performance of the algorithms. Matrix multiplication is a very simple algorithm with upper and lower bounded Q(n3) complexity. If you are not familiar with the algorithm I would suggest first to read the Matrix multiplication at Wikipedia. CPU Cache is a low capacity very fast storage which physical location is very close to the CPU. CPU caches make our programs run faster in three different ways:

  1. The program operations that are executed repeatedly are cached and therefore our program runs faster because the new instructions are not fetched from the slow memory but the cache – this is mainly relevant to a specialized instruction cache and is not in our focus since we will not deal with the complexity optimizations.
  2. The repeatedly accessed variables in the code are cached and the subsequent access is faster – this is known as temporal locality.
  3. Variables that are located next to each other in memory, such as array elements, are accessed faster. When the first array element is accessed for the first time in the program, that element together with the subsequent few array elements are brought into the cache – this is known as spatial locality.

For more information about how cache is implemented to provide the above features you can refer again to the Wikipedia entry CPU Cache or a very nice article by Jon Stokes titled Understanding CPU caching and performance.

The Matrix Multiplication Algorithms

Now, after a brief overview, let's return back to our matrix multiplication algorithm. Here I have two algorithms:

  1. The well known STANDARD algorithm for matrix multiplication that most of us are taught at high school.
  2. An OPTIMIZED algorithm, which gets advantage from the spatial locality of the array members (i.e. the (3) way caches make programs run faster) by traversing the matrices' elements in a different order than in the STANDARD algorithm.

After multiplying matrices Am,n and Bn,k each entry ci,j in the resultant matrix Cm,k is:

ci,j=ai,0.b0,j + ai,1.b1,j + .. + ai,n.bn,j, where (0 ≤ i ≤ m) and (0 ≤ i ≤ k).

 

The Standard Algorithm

Below is the standard algorithm for multiplying 2 square matrices. It resembles the formula above by computing each element in matrix C in by traversing the matrix C only one time.

 

1: for (k = 0; k < n; k++)

2: {

3:    for (i = 0; i < n; i++)

4:    {

5:        for (j = 0; j < n; j++)

6:        {

7:           c[k][i] = c[k][i] + a[k][j]*b[j][i];

8:        }

9:    }

10: }

 

The Optimized Algorithm

Below is the standard algorithm for multiplying 2 square matrices. This algorithm incrementally computes the elements in matrix C by iterating on matrix C N2 times. The two algorithms are different only at line 7. The optimized algorithm traverses matrix B along columns, thus benefiting from the spatial locality. Also, it traverses matrix C multiple times thus benefiting from temporal locality of L2.

1: for (k = 0; k < n; k++)

2: {

3:    for (i = 0; i < n; i++)

4:    {

5:       for (j = 0; j < n; j++)

6:       {

7:          c[i][j] = c[i][j] + a[i][k]*b[k][j];

8:       }

9:    }

10: }

 

Performance Results

The table below shows the performance of the two algorithms for different sizes of the matrices. For simplicity, here we assume that matrices are square. Also the table shows the cache misses obtained with VTune profiling tool. The characteristics of the computer I run the application are 1.66GHz Dual Core CPU, with 2MB L2 cache per core and 32KB L1 instruction and data cache. I compiled the source using the Microsoft Visual C++ compiler. The L1 miss rate is per retired instruction and L2 miss rate is per referenced data.

Size

MB

Standard

Optimized

Time

L1 Miss

L2 Miss

Time

L1 Miss

L2 Miss

128×128

64K

0.1

5.5%

0%

0.09

0.7%

0%

256×256

256K

0.23

7.3%

0%

0.2

0.5%

0%

512×512

1MB

1.5

7.1%

0.1%

1.5

0.5%

0.2%

1024×1024

4MB

44.2

7.2%

12.5%

7.9

0.5%

0.6%

2048×2048

16MB

394.7

10.1%

12.5%

63.5

0.5%

0.6%

 Cache efficient matrix multiplication performance

 

Why the Optimized Algorithm is Faster?

Now let's try to explain why the optimized algorithm runs faster. From the table above, we see that for small numbers the performance hurt is not evident. The reason for this is that matrices are small enough to fit almost all in the L1 cache and all in L2 cache.

1st major reason for the performance penalty with big matrices in the standard algorithm comes from L1 cache. The standard algorithm traverses matrix B along its columns and this way not benefiting from spatial locality in the L1 cache. 2nd performance penalty comes from L2 cache. The standard algorithm does not benefit both from the spatial locality because it traverses the matrix B along its columns and whenever a non-cached row is accessed it should be cached (note this is valid for both L1 and L2). Moreover, the standard matrix does not benefit from the temporal locality as it accesses each element of matrix C only once (not repeatedly). Although the element being computed element (c[k][j]) is stored in a register obviously this doesn't contribute to the performance at all.

The optimized algorithm is not as optimal on traversing matrix A, as is in the standard algorithm but the gained performance from the other optimizations makes it negligible.

Conclusion

From this small example we can see that, besides the theoretical complexity dimension as studied and analyzed in the "Introduction to Algorithms", the delivered performance of algorithms depends also on the micro architectural details of our computers. And to write performance efficient programs we should know the underlying architectural details. This algorithm for example could be further refined to benefit from the cache line sizes but this would make it micro-architectural (CPU) dependent and thus run slower in other processors.

Downloads

The source code of the matrices is available here: MatrixMuliplay.

Guide for writing diploma, master or PhD thesis

A while ago I prepared an article "How to Write Diploma, Master or PhD Thesis?" that briefly explain how to organize the contents of your thesis. I don’t host the article here in the blog because of the possible changes that I would make to keep it up to date. So those interested can go and throw a look on it. Hope it would be hopeful to better structure and organize your thesis.

Better small fonts in Ubuntu 8.10 (intrepid)

After an out of the box install of Kubuntu 8.10 Intrepid all my fonts seemed to me too large. These large fonts don’t seem very elegant and thankfully I also don’t have vision problems with my eyes. The article "The Absurdity of GNOME Font Sizes" discusses about the big fonts in ubuntu but does not tell much how to make our fonts smaller. So I decided to look around the settings what do we have and after checking my appearance settings I could set nice looking smaller fonts globally on my desktop.I achieved this nice effect from

"System settings->Appearance->Fonts".

Here you have to:

  1. Enable "anti-aliasing" or also font smoothing. This makes your fonts more smooth – less edged – and the text is more easy to read.
  2. From the extra configuration options for anti-aliasing disable "exclude range" and enable "use sub-pixel rendering". In the first option the default range is small and will not affect the small fonts – the result will be that letters will look edged. Sub-pixel rendering enhances the quality. Current computers are powerful enough so that these changes will not make any visible performance impact.
  3. Now you have to also choose: "Force fonts DPI" to be 96 DPI. Actually this is what makes your fonts look smaller. I use 1400×1050 so this DPI for me looks pretty OK. If you have lower resolution and want smaller fonts probably you may either think of encreasing your desktop resolution or tweeak the fonts size DPI manually to some lower value of 96DPI. The article "How to change the X11 DPI under kUbuntu" tells more about custom DPI settings.
  4. Then you have to logoff and login so that chages take effect.

I wished I put some screen shots to demonstrate the effect but I am lazy now to revert back and forth with my configuration. Probably later.

 

Cell phone services: primitive in Cuba and advanced in US?

I have read an article "In Cuba, Cellphone Calls Go Unanswered" at Washington Post by William Booth that reminded me for the time in Bulgaria back in 1980s. Because of the closed market it was difficult to find and buy things that are not produced by the countries from the ex Soviet Union, for example jeans or coca cola. But I found the article somehow biased with an implicit attempt to condemn the regime in Cuba and humiliate the Cubans by laughing at the situation.

I haven’t been in Cuba yet but knowing what was in my country I do believe the story about the mobile phones is true. For example, I remember that in 1987 we registered in a waiting queue for landline phone and we got the line in 1992 and the line cost like 2-3 monthly salaries. Also finding a phone was problem, too. In 1980s it was a symbol of status wearing jeans or having electronic watch.

But what I don’t like in the article is that it discusses just one weak point in Cuba and strong point in the States – the mobile phones. I wished Mr. William Booth mention about the health care and education system in both USA and Cuba! Which is better, to not be able to talk on mobile phone or be refused medical treatment and left to die because you don’t have health insurance? Both are bad! There is no doubt that the communist system proved to not work, but I don’t think that the US model of capitalist system proved to work.

On the other side, if the intention of the article was not to show that the system in Cuba is “bad” and the system in the States it “good” but purely technical with intent to show the level of advancement in technology – I would expect Mr. William Booth mention about the mobile services in Europe and Japan. This would be again fair enough. Although the States is a world leading country in many fields of technology – mobile phones is not one of them.