rain of code

FPGA Clocking Resources (Xilinx Spartan-6)

2011-08-09T23:20:00.002+08:00

Reference:

Spartan-6 FPGA Clocking Resources User Guide

Other Useful Resources:

Start Stealing - Memory Instruction

2011-08-07T02:49:00.003+08:00

UART Controller: Baud Detector (to avoid glitch)

2011-07-02T01:31:00.000+08:00

UART Controller: Control Unit (Rx/Tx Buffer)

2011-06-27T00:00:00.000+08:00

UART Controller: Data Flow

2011-06-25T00:53:00.000+08:00

Floating-point Multiplication Resources on FPGA

2011-01-04T01:55:00.109+08:00

1. Introduction

As I'm thinking of using floating-point operations for my processor other than just integer operations, it's kind of a good idea if I start with feasibility study especially on the resources that are required since I have only a low cost FPGA board with quite limited slices. The one that I have is SP601 board with XC6SLX16 FPGA chip. Table 1.1 shows the resources it has.

Table 1.1: XC6SLX16 FPGA Resources

On the study, I just focus on floating-point multiplication for both single and double precisions using provided IP from Xilinx that is based on IEEE-754 standard. For each precision, I try to compare two types of family optimizations, no-usage which uses logic cells only and full-usage which uses combination of DSP slices and logic cells. Based on the precisions and family optimizations, I collect data for area utilization (slices, FFs and LUTs), selectable latencies, maximum frequency and power consumption. All data are based on software reports, none of them are from hardware measurements.

For the software, I use ISE WebPack 12.3 installed on Ubuntu 10.10 Linux for 64-bit processor. None of the ISE default settings I have changed for any kind of optimizations and I don't define any constraints other than clock frequency that is required to generate power report. The frequencies are chosen to be lower than maximum achievable frequency reported during synthesizing the design so they won't force ISE to do extra work that may lead to extra area used. I only change Map Property to generate detailed map report so I can get slice utilization by hierarchy.

I generate four modules using LogiCore, two single precisions (SPs) and two double precisions (DPs) with no-usage (NU) and full-usage (FU) family optimizations combination so I have SP/NU, SP/FU, DP/NU and DP/FU modules with all handshaking, control and exception signals activated. I encapsulate each module using VHDL and change the signal names so they can be easily modified internally without affecting other components. Another benefit of component encapsulation is when generating area utilization and power consumption reports, I can easily get resources that are used by the component itself. Since I have encapsulated only floating-point multiplication module, all data presented in this study don't include I/O registers, I/O buffers, clock buffer and other logic cells supporting them. As shown in Figure 1.1, dp_mul_ip_PM is the module generated by LogiCore and dp_mul_1 is the encapsulating component so all fds as I/O registers and other modules like I/O and clock buffers (are not shown in the figure and located even outside I/O registers) will not be included to be the resources needed by the multiplication component.

Figure 1.1: Double Precision Floating-point Multiplication RTL Schematic

All multiplication components have been simulated using Xilinx ISim provided by ISE WebPack. Figure 1.2 shows simulation waveform of multiplication between 1.5d (0x3FF8000000000000) and 0.3d (0x3FD3333333333333) resulting 0.45d (0x3FDCCCCCCCCCCCCC). The multiplication uses double precisions, full-usage family optimization and 27-latency. At the beginning, after doing synchronous reset (sreset signal goes HIGH), inready signal goes LOW for a moment indicates the component is not ready to receive inputs. It's also a good time to prepare both of the inputs (a and b buses) to be calculated and when inready signal goes HIGH, ask the component to start calculating by setting run signal to HIGH. 27 clocks later, result bus starts showing calculation result and the result is ready indicated by outready signal turns HIGH.

Figure 1.2: Double Precision Floating-point Multiplication Simulation Waveform

2. Precision and Family Optimization Selections

When generating multiplication modules using LogiCore, family optimization selections specify whether DSP slices should be used. Only no-usage selection will not use DSP slices at all, instead, it uses only logic cells like LUTs and FFs. The other selections like medium-usage, full-usage and max-usage selections use different number of DSP slices. For full-usage selection, my FPGA uses four DSP slices for single precision and 16 DSP slices for double precision. It means my FPGA supports up to eight single precision or two double precision components when using full-usage selection.

Figure 2.1: Number of DSP Slices Used by Different Precisions and Family Optimizations

Figure 2.2, 2.3 and 2.4 show double precision with no-DSP-usage uses most slices as much as one third of my entire FPGA slices since single precision with full-DSP-usage uses smallest amount of slices. Double precision with full-DSP-usage uses less slices compare to single precision with no-DSP-usage. Figure 2.3 shows that number of FFs can be pushed as low as possible regardless the precision used or family optimization selected.

Figure 2.2: Number of Slices Used by Different Precisions and Family Optimizations

Figure 2.3: Number of FFs Used by Different Precisions and Family Optimizations

Figure 2.4: Number of LUTs Used by Different Precisions and Family Optimizations

Figure 2.5 and 2.6 show double precision with full-DSP-usage has wider latency selections to reach comparable maximum frequency with the others that have about the same maximum latency.

Figure 2.5: Number of Selectable Latency for Different Precisions and Family Optimizations

Figure 2.6: Frequency of Different Precisions and Family Optimizations

Figure 2.7 shows power consumption can be push down as low as possible for power critical design and no-DSP-usage can be power-hungry components.

Figure 2.7: Power Consumption of Different Precisions and Family Optimizations

Figure 2.2 to 2.7 show that full-DSP-usage for single or double precision uses much lesser slices while maintaining higher frequency (up to 50 MHz), higher latency selections and lower power consumption (up to 40 mW) compared to no-DSP-usage.

3. Latency Selections

Figure 3.1 to 3.4 show that one way to increase maximum frequency is by increasing latency but this will also increase number of FFs used for pipelining. One thing good to know is that multiplication module is able to use full pipeline without having to wait few steps from one calculation to the next like what square-root module does. The full pipeline simulation is shown in Figure 3.5.

As Spartan-6 slice contains four LUTs and eight FFs, increasing number of FFs do not affect number of slices used by so much. Only when number of FFs increase up to two times number of LUTs, it will start affecting number of slices used noticeably. From Figure 3.1 to 3.4, only components with full-DPS-usage have the number of FFs reach up to 1.5 times of the number of LUTs so for all components the rest of FFs can be shared with other components. But if for some reasons, you want to group every multiplication component without sharing the slices with other components, choosing higher latency is a good idea to increase maximum frequency. Furthermore, for components with full-DSP-usage, increasing latency reduces number of slices. Special case for single precision with no-DSP-usage as shown in Figure 3.1, choosing latency higher than 4 may not beneficial anymore.

Figure 3.1: Latency to Area Utilization and Frequency for SP/NU

Figure 3.2: Latency to Area Utilization and Frequency for SP/FU

Figure 3.3: Latency to Area Utilization and Frequency for DP/NU

Figure 3.4: Latency to Area Utilization and Frequency for DP/FU

Figure 3.5: Full Pipeline Simulation of Multiplication Operation

Latency selections effecting power are discussed together with frequency selections in section 4.

4. Frequency Selections

As discussed in the introduction, frequencies are chosen to be lower than maximum frequency reported during synthesizing the design so they will not affect area utilization. As shown in Figure 4.1, some missing surfaces (mostly at the low latencies and high frequencies) are because the components can not meet such frequencies.

For no-DSP-usage, higher frequency increases power consumption and higher latency reduces it. But for full-DSP-usage, both higher frequency and latency just slightly increase power consumption.

Figure 4.1: Latency and Frequency to Power Consumption

Clock, IOs and quiescent power consumptions are also increased as frequency is getting higher, as for frequency ranging from 12.5 up to 200MHz, they are about 0.5 to 20mW, 7.5 to 120mW, and 14.96 to 16.37mW respectively.

5. Future FPGAs

Spartan-6 and Virtex-6 families are what currently in the market and Artix-7, Kintex-7 and Virtex-7 families are coming. Figure 5.1 and 5.2 show number of slices and DSP slices for each family. As I'm doing my processor only for hobby, I always look out for low cost FPGAs. It seems that even Artix-7 and Kintex-7 will have more slices and much more DSP slices compared to my Spartan-6. It's not really a good sign yet as they haven't put down the price.

Figure 5.1: Number of Slices for Current and Future FPGA Families

Figure 5.2: Number of DSP Slices for Current and Future FPGA Families

6. Conclusion

Flexibility to use or not to use DSP slices is provided when generating multiplication module using LogiCore.
Different floating-point operations have different maximum DSP slices that can be used.
Full-DSP-usage for single or double precision uses much lesser slices (up to four times) while maintaining higher frequency (up to 20%), higher latency selections and lower power consumption (up to five times) compared to no-DSP-usage.
Increasing latency will also increase frequency and FFs but not so much on the slices. Even when using maximum latency, 25% to 50% of the FFs are not used for all used slices.
For design that groups every multiplication component without sharing the slices with other components, choosing higher latency is a good idea to achieve higher frequency.
For no-DSP-usage, increasing latency reduces number of slices used and power consumption.
There is a case when choosing latency higher than certain value will not beneficial anymore in term of frequency increment.
Higher frequency is always resulting higher power consumption, just for full-DSP-usage, the increment is not significant.
Future FPGA families will have more slices and much more DSP slices.

7. References

8. Useful Tools

IEEE-754 Calculators

Configuring Target Device (iMPACT) on Ubuntu

2010-10-24T17:03:00.001+08:00

Today is a lovely day! It marks for the first time I get my FPGA binary file successfully be programmed into my FPGA board using Linux. FYI, I'm using Xlinx ISE WebPack 12.3 and Ubuntu 10.10. I follow step-by-step tutorial from Stube posted on Xilinx ISE WebPack 12.2 on Ubuntu 10.04 LTS. Thanks, Stube!

Downloading FPGA Binary File

My FPGA and Linux Machine

Changing Font Size And Font Family On Xilinx ISE Software

2010-10-24T13:08:00.000+08:00

I'm using Xilinx ISE WebPack 12.3 and Ubuntu 10.10. In order to change the font size and font family, you need qtconfig tool installed on your Ubuntu. qtconfig is Qt Configuration tool as ISE software on Linux is developed using Qt. I'm using qtconfig for Qt version 4 and it's working fine. Open Ubuntu Software Center, find qtconfig and install it.

Ubuntu Software Center With qtconfig Installed

After you get qtconfig installed, open Terminal and execute qtconfig. A new Qt Configuration window will pop up. You can go to Font tab and change the font size and font family as you wish. Remember, you need to close the window and choose save in order for your changes to take place.

qtconfig In Action

XMT-PRAM Summary

2010-09-19T05:27:00.003+08:00

Reference:

Cell/BE PPU Summary

2010-05-20T23:55:00.004+08:00

Cell/BE PPU Summary

Calculator for iPad

2010-05-10T00:19:00.004+08:00

Reference: Stanford University - CS 193P iPhone Application Development.

C/C++ vs Objective-C

2010-04-30T23:57:00.008+08:00

Reference : Learning Objective-C: A Primer

Slider!

2010-04-19T22:28:00.003+08:00

My first and very own iPad application. Slider!

iPhone/iPad Simulator

Setting Up PostgreSQL for Django

2009-12-13T21:27:00.015+08:00

In this tutorial, I'm using Python 2.6, Django 1.1.1 and PostgreSQL 8.3.8.

[eka@localhost mysite]$ python --version
Python 2.6
[eka@localhost mysite]$ django-admin --version
1.1.1
[eka@localhost mysite]$ psql --version
psql (PostgreSQL) 8.3.8
contains support for command-line editing

After PostgreSQL installed on my Linux, I had gotten postgres Linux user setted up for me. Using postgres user account, I can do database initialization, user creation, and database creation.

Following are few steps to get PostgreSQL ready for Django.

Creating Directory for PostgreSQL Data

I create my PostgreSQL at /usr/local/pgsql/data directory owned by postgres Linux user. To do so you have to login as Linux superuser (root).

[eka@localhost Documents]$ su
Password: 
[root@localhost Documents]# mkdir /usr/local/pgsql/data
[root@localhost Documents]# chown postgres /usr/local/pgsql/data
[root@localhost Documents]# exit
exit
[eka@localhost Documents]$

Initializing Database Cluster, Creating New User and Database

Use initdb, createuser, and createdb Linux commands to respectively initialize database cluster, creating new user, and creating new database.

[eka@localhost Documents]$ su postgres
Password: 

bash-4.0$ initdb -D /usr/local/pgsql/data
could not change directory to "/home/eka/Documents"
The files belonging to this database system will be owned by user "postgres".
This user must also own the server process.

The database cluster will be initialized with locale en_US.UTF-8.
The default database encoding has accordingly been set to UTF8.
The default text search configuration will be set to "english".

fixing permissions on existing directory /usr/local/pgsql/data ... ok
creating subdirectories ... ok
selecting default max_connections ... 100
selecting default shared_buffers/max_fsm_pages ... 24MB/153600
creating configuration files ... ok
creating template1 database in /usr/local/pgsql/data/base/1 ... ok
initializing pg_authid ... ok
initializing dependencies ... ok
creating system views ... ok
loading system objects' descriptions ... ok
creating conversions ... ok
creating dictionaries ... ok
setting privileges on built-in objects ... ok
creating information schema ... ok
vacuuming database template1 ... ok
copying template1 to template0 ... ok
copying template1 to postgres ... ok

WARNING: enabling "trust" authentication for local connections
You can change this by editing pg_hba.conf or using the -A option the
next time you run initdb.

Success. You can now start the database server using:

    postgres -D /usr/local/pgsql/data
or
    pg_ctl -D /usr/local/pgsql/data -l logfile start

bash-4.0$ cd /usr/local/pgsql/data/

bash-4.0$ createuser -P django_user
Enter password for new role: 
Enter it again: 
Shall the new role be a superuser? (y/n) n
Shall the new role be allowed to create databases? (y/n) y 
Shall the new role be allowed to create more new roles? (y/n) n

bash-4.0$ createdb -O django_user django_db

bash-4.0$ exit

[eka@localhost Documents]$

Setting Up PostgreSQL Information for Django

After you create Django project followed by Django application, you will have settings.py file created for you. You need to put all PostgreSQL information in it. I'm using psycopg version 2 as the interpreter between Django and PostgreSQL so I have to put in postgresql_psycopg2 instead of postgresql for the database engine.

[eka@localhost mysite]$ pwd
/home/eka/workspace/programming/django/test_django/mysite
[eka@localhost mysite]$ ls -l
total 24
-rw-r--r--. 1 eka eka    0 2009-11-08 11:36 __init__.py
-rw-r--r--. 1 eka eka  166 2009-11-08 18:55 __init__.pyc
-rwxr-xr-x. 1 eka eka  546 2009-11-08 11:36 manage.py
-rw-r--r--. 1 eka eka 2823 2009-12-13 16:17 settings.py
-rw-r--r--. 1 eka eka 1771 2009-12-05 20:31 settings.pyc
-rw-r--r--. 1 eka eka  542 2009-11-08 11:36 urls.py
-rw-r--r--. 1 eka eka  266 2009-11-08 18:57 urls.pyc
[eka@localhost mysite]$ vim settings.py

...
DATABASE_ENGINE = 'postgresql_psycopg2'       # 'postgresql_psycopg2', 'postgresql', 'mysql', 'sqlite3' or 'oracle'.
DATABASE_NAME = 'django_db'                   # Or path to database file if using sqlite3.
DATABASE_USER = 'django_user'                 # Not used with sqlite3.
DATABASE_PASSWORD = 'django_user_pwd'         # Not used with sqlite3.
DATABASE_HOST = 'localhost'                   # Set to empty string for localhost. Not used with sqlite3.
DATABASE_PORT = ''                            # Set to empty string for default. Not used with sqlite3.
...

Opening Access for Local PC

As the default, PostgreSQL will not allow local PC to access the database. To allow local PC to access database you have to edit pg_hba.conf file inside PostgreSQL data directory and change all METHOD column with trust value for all TYPE column with local value. You have to login as Linux superuser (root) to do this.

[eka@localhost Documents]$ su
Password: 
[root@localhost Documents]# vim /var/lib/pgsql/data/pg_hba.conf

...
# TYPE  DATABASE    USER        CIDR-ADDRESS          METHOD

# "local" is for Unix domain socket connections only
local   all         all                               trust # ident sameuser
# IPv4 local connections:
host    all         all         127.0.0.1/32          trust # ident sameuser
# IPv6 local connections:
host    all         all         ::1/128               trust # ident sameuser
...

Don't forget to restart PostgreSQL server if it's already running or start it if it hasn't.

[root@localhost mysite]# /etc/init.d/postgresql start
Starting postgresql service:                               [  OK  ]
[root@localhost mysite]# exit
exit
[eka@localhost mysite]$

Synchronizing Django Database

You can now synchronizing Django data to PostgreSQL database using manage.py file inside your Django application directory with syncdb parameter.

[eka@localhost mysite]$ pwd
/home/eka/workspace/programming/django/test_django/mysite
[eka@localhost mysite]$ ls -l
total 24
-rw-r--r--. 1 eka eka    0 2009-11-08 11:36 __init__.py
-rw-r--r--. 1 eka eka  166 2009-11-08 18:55 __init__.pyc
-rwxr-xr-x. 1 eka eka  546 2009-11-08 11:36 manage.py
-rw-r--r--. 1 eka eka 2835 2009-12-13 17:45 settings.py
-rw-r--r--. 1 eka eka 1777 2009-12-13 17:45 settings.pyc
-rw-r--r--. 1 eka eka  542 2009-11-08 11:36 urls.py
-rw-r--r--. 1 eka eka  266 2009-11-08 18:57 urls.pyc
[eka@localhost mysite]$ ./manage.py syncdb
Creating table auth_permission
Creating table auth_group
Creating table auth_user
Creating table auth_message
Creating table django_content_type
Creating table django_session
Creating table django_site

You just installed Django's auth system, which means you don't have any superusers defined.
Would you like to create one now? (yes/no): yes
Username (Leave blank to use 'eka'): 
E-mail address: ...
Password: 
Password (again): 
Superuser created successfully.
Installing index for auth.Permission model
Installing index for auth.Message model
[eka@localhost mysite]$

Setting Up MySQL for Django

2009-11-22T23:00:00.007+08:00

In this tutorial, I'm using Python 2.6, Django 1.1.1 and MySQL 14.14.

[eka@localhost mysite]$ python --version
Python 2.6
[eka@localhost mysite]$ django-admin --version
1.1.1
[eka@localhost mysite]$ mysql --version
mysql  Ver 14.14 Distrib 5.1.37, for redhat-linux-gnu (x86_64) using readline 5.1

First of all, you need super user or root access to continue this tutorial. After login as super user, switch to MySQL console using mysql command to create new user, create new database and grant the new user access to the new database.

[eka@localhost mysql]$ su
Password: 
[root@localhost mysql]# mysql
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 55
Server version: 5.1.37 Source distribution

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql>

Creating New User

Use CREATE USER command to create new user and SET PASSWORD command to set new password to the new user.

mysql> SELECT Host,User,Password from mysql.user;
+-----------------------+------+----------+
| Host                  | User | Password |
+-----------------------+------+----------+
| localhost             | root |          | 
| localhost.localdomain | root |          | 
| 127.0.0.1             | root |          | 
| localhost             |      |          | 
| localhost.localdomain |      |          | 
+-----------------------+------+----------+
5 rows in set (0.00 sec)

mysql> CREATE USER 'eka'@'localhost';
Query OK, 0 rows affected (0.00 sec)

mysql> SET PASSWORD FOR 'eka'@'localhost' = password('eka');
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT Host,User,Password from mysql.user;
+-----------------------+------+------------------+
| Host                  | User | Password         |
+-----------------------+------+------------------+
| localhost             | root |                  | 
| localhost.localdomain | root |                  | 
| 127.0.0.1             | root |                  | 
| localhost             |      |                  | 
| localhost.localdomain |      |                  | 
| localhost             | eka  | 7bb7afcb215939e3 | 
+-----------------------+------+------------------+
6 rows in set (0.00 sec)

mysql>

Creating New Database

Use CREATE DATABASE command to create new database.

mysql> SHOW DATABASES;
+--------------------+
| Database           |
+--------------------+
| information_schema | 
| mysql              | 
| test               | 
+--------------------+
3 rows in set (0.00 sec)

mysql> CREATE DATABASE mysite;
Query OK, 1 row affected (0.00 sec)

mysql> SHOW DATABASES;
+--------------------+
| Database           |
+--------------------+
| information_schema | 
| mysite             | 
| mysql              | 
| test               | 
+--------------------+
4 rows in set (0.00 sec)

mysql> mysql> SHOW DATABASES;
+--------------------+
| Database           |
+--------------------+
| information_schema | 
| mysql              | 
| test               | 
+--------------------+
3 rows in set (0.00 sec)

mysql> CREATE DATABASE mysite;
Query OK, 1 row affected (0.00 sec)

mysql> SHOW DATABASES;
+--------------------+
| Database           |
+--------------------+
| information_schema | 
| mysite             | 
| mysql              | 
| test               | 
+--------------------+
4 rows in set (0.00 sec)

mysql>

Granting User To Access Databse

Use GRANT command to grant user specific access to database. In following example, I'll give all accesses to the new user. You can limit user access as you like. The list of all accesses can be found at GRANT documentation.


mysql> SHOW GRANTS for 'eka'@'localhost';
+-----------------------------------------------------------------------------------+
| Grants for eka@localhost                                                          |
+-----------------------------------------------------------------------------------+
| GRANT USAGE ON *.* TO 'eka'@'localhost' IDENTIFIED BY PASSWORD '7bb7afcb215939e3' | 
+-----------------------------------------------------------------------------------+
1 row in set (0.00 sec)

mysql> GRANT ALL ON mysite.* TO 'eka'@'localhost';
Query OK, 0 rows affected (0.00 sec)

mysql> SHOW GRANTS for 'eka'@'localhost';
+-----------------------------------------------------------------------------------+
| Grants for eka@localhost                                                          |
+-----------------------------------------------------------------------------------+
| GRANT USAGE ON *.* TO 'eka'@'localhost' IDENTIFIED BY PASSWORD '7bb7afcb215939e3' | 
| GRANT ALL PRIVILEGES ON `mysite`.* TO 'eka'@'localhost'                           | 
+-----------------------------------------------------------------------------------+
2 rows in set (0.00 sec)

mysql>

Editing Django Settings File

Until now, a new database is ready to use. You then can tell Django to use the new database by editing settings.py file. The file is inside your new Django project directory. Off course you have to create new project first if you haven't. In following example, I have mysite as my project name.

mysql> quit
Bye
[root@localhost mysite]# exit
exit
[eka@localhost mysite]$ ls -l
total 24
-rw-r--r--. 1 eka eka    0 2009-11-08 11:36 __init__.py
-rwxr-xr-x. 1 eka eka  546 2009-11-08 11:36 manage.py
-rw-r--r--. 1 eka eka 2799 2009-11-21 22:49 settings.py
-rw-r--r--. 1 eka eka  542 2009-11-08 11:36 urls.py
[eka@localhost mysite]$

Edit settings.py file as follow.

DATABASE_ENGINE = 'mysql'      # 'postgresql_psycopg2', 'postgresql', 'mysql', 'sqlite3' or 'oracle'.
DATABASE_NAME = 'mysite1'      # Or path to database file if using sqlite3.
DATABASE_USER = 'eka'          # Not used with sqlite3.
DATABASE_PASSWORD = 'eka'      # Not used with sqlite3.
DATABASE_HOST = 'localhost'    # Set to empty string for localhost. Not used with sqlite3.
DATABASE_PORT = ''             # Set to empty string for default. Not used with sqlite3.

Synchronizing Database

Telling Django to do synchronization with the new database using python manage.py syncdb command.

[eka@localhost mysite]$ python manage.py syncdb
Creating table auth_permission
Creating table auth_group
Creating table auth_user
Creating table auth_message
Creating table django_content_type
Creating table django_session
Creating table django_site

You just installed Django's auth system, which means you don't have any superusers defined.
Would you like to create one now? (yes/no): yes
Username (Leave blank to use 'eka'): eka
E-mail address: eka.a.kurniawan@gmail.com
Password: 
Password (again): 
Superuser created successfully.
Installing index for auth.Permission model
Installing index for auth.Message model
[eka@localhost mysite]$

That's all. Enjoy it.

Xilinx Spartan-6 FPGA

2009-09-29T23:09:00.000+08:00

My second FPGA board after Xilinx Spartan-2 in 2004.

Books (0909292307)

2009-09-29T23:07:00.000+08:00

Sieve of Eratosthenes

2009-08-08T01:13:00.005+08:00

Sieve of Eratosthenes
(κόσκινον Ἐρατοσθένους)

Sift the Twos and sift the Threes,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Wikipedia - Sieve of Eratosthenes

Mathematics is Beautiful

2009-07-30T23:58:00.004+08:00

""I thought, whatever mathematics is, it's must be beautiful.""

SEED - Mathematics

Fixing "could not read symbols" on Cell Processor Binary Linking

2009-07-24T16:12:00.012+08:00

I faced linking problem when I was trying to compile C code into Cell Processor binary file. Actually, I was following an example from a book titled Programming The Cell Processor by Matthew Scarpino.

Following is the error that I faced.

[eka@localhost ppu_project]$ ppu-ld a.o -o a /usr/lib64/crt1.o /usr/lib64/crti.o /usr/lib/crtn.o --dynamic-linker /lib64/ld64.so.1 -lc
ppu-ld: /usr/lib64/crt1.o: Relocations in generic ELF (EM: 62)
/usr/lib64/crt1.o: could not read symbols: File in wrong format

Error on Linking Process

Most of the time, the error is caused by linking different processor type object files. I believe the example works fine if I do it on PS3 which the crt1.o, crti.o and crtn.o are Cell Processor object files. Unfortunately, I haven't get my PS3 yet. I did it on my MacBook Pro (Intel Processor) using Fedora 11.

For Fedora, Cell SDK provides the Cell Processor object files at:
- /opt/cell/sysroot/usr/lib64/ directory for 64-bit version and
- /opt/cell/sysroot/usr/lib/ directory for 32-bit version

The linking problem was solved by using appropriate object files.

[eka@localhost ppu_project]$ ppu-ld a.o -o a /opt/cell/sysroot/usr/lib64/crt1.o  /opt/cell/sysroot/usr/lib64/crti.o /opt/cell/sysroot/usr/lib64/crtn.o --dynamic-linker /lib64/ld64.so.1 -lc

Working Linking Process

This how I found it. I did one shot compilation process by using following command and it worked.

[eka@localhost ppu_project]$ ppu-gcc a.c -Ihead_dir -o a.out

One Shot Compilation Process

I then tried to spy on how the one shot compilation process done it; with adding -v compilation option. Look at the words highlighted using blue color.

[eka@localhost ppu_project]$ ppu-gcc a.c -v -Ihead_dir -o a.out
Using built-in specs.
Target: ppu
Configured with: ../toolchain/gcc/configure --prefix=/opt/cell/toolchain --mandir=/opt/cell/toolchain/man --infodir=/opt/cell/toolchain/info --with-sysroot=/opt/cell/sysroot --with-as=/opt/cell/toolchain/bin/ppu-as --with-ld=/opt/cell/toolchain/bin/ppu-ld --enable-threads --with-system-zlib --disable-checking --enable-__cxa_atexit --disable-libunwind-exceptions --enable-languages=c,c++,fortran,ada --disable-nls --enable-clocale=gnu --enable-version-specific-runtime-libs --with-long-double-128 --program-prefix=ppu- --disable-bootstrap --build=i686-pc-linux-gnu --target=ppu
Thread model: posix
gcc version 4.1.1
 /opt/cell/toolchain/libexec/gcc/ppu/4.1.1/cc1 -quiet -v -Ihead_dir -D__unix__ -D__gnu_linux__ -D__linux__ -Dunix -D__unix -Dlinux -D__linux -Asystem=linux -Asystem=unix -Asystem=posix a.c -quiet -dumpbase a.c -auxbase a -version -o /tmp/cclPY7x1.s
ignoring nonexistent directory "/opt/cell/sysroot/usr/local/include"
ignoring nonexistent directory "/opt/cell/toolchain/lib/gcc/ppu/4.1.1/../../../../ppu/include"
#include "..." search starts here:
#include <...> search starts here:
 head_dir
 /opt/cell/toolchain/lib/gcc/ppu/4.1.1/include
 /opt/cell/sysroot/usr/include
End of search list.
GNU C version 4.1.1 (ppu)
 compiled by GNU C version 4.1.2 20071124 (Red Hat 4.1.2-42).
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: 1a909946e913637678412cf140132c95
 /opt/cell/toolchain/bin/ppu-as -a64 -mppc64 -many -V -Qy -o /tmp/ccoiPg2T.o /tmp/cclPY7x1.s
GNU assembler version 2.18.50 (powerpc64-linux) using BFD version (GNU Binutils) 2.18.50.20080408
 /opt/cell/toolchain/libexec/gcc/ppu/4.1.1/collect2 --sysroot=/opt/cell/sysroot --eh-frame-hdr -V -Qy -m elf64ppc -dynamic-linker /lib64/ld64.so.1 -o a.out /opt/cell/sysroot/usr/lib/../lib64/crt1.o /opt/cell/sysroot/usr/lib/../lib64/crti.o /opt/cell/toolchain/lib/gcc/ppu/4.1.1/crtbegin.o -L/opt/cell/toolchain/lib/gcc/ppu/4.1.1 -L/opt/cell/sysroot/lib/../lib64 -L/opt/cell/sysroot/usr/lib/../lib64 /tmp/ccoiPg2T.o -lgcc --as-needed -lgcc_s --no-as-needed -lc -lgcc --as-needed -lgcc_s --no-as-needed /opt/cell/toolchain/lib/gcc/ppu/4.1.1/crtsavres.o /opt/cell/toolchain/lib/gcc/ppu/4.1.1/crtend.o /opt/cell/sysroot/usr/lib/../lib64/crtn.o
GNU ld (GNU Binutils) 2.18.50.20080408
  Supported emulations:
   elf64ppc
   elf32ppclinux
   elf32ppc
   elf32ppcsim
   elf32_spu

One Shot Compilation Process with -v Option

Actually, I just found out that, for example, on PS3 (Cell Processor) Linux machine you do linking your code to /usr/spu/lib/, on MacBook Pro (Intel Processor) Linux machine you have to add /opt/cell/sysroot/ at the beginning so it becomes /opt/cell/sysroot/usr/spu/lib/.

Right Click on MacBook Pro Using Fedora 11

2009-07-05T14:57:00.007+08:00

I'm using Fedora 11 for x86_64 processor type on my MacBook Pro. To do right click, I can simply put two fingers on track-pad and press click.

Source: Fedora Forum - 212903

Developing Android using C/C++ on Mac

2009-06-13T13:24:00.061+08:00

Before started, I have some notes that you have to aware of.

Firstly, in this tutorial I will just show you on how to compile and run C/C++ code on Android Emulator. On how to set up your Mac, install repository, and build the code; they have been explained in so amazingly detail at Get Source web site from Android Open Source Project. Yet, there's still a little tiny problem to overcome but it's not really an issue.

Secondly, until this time, Android still doesn't support C/C++ GUI API at it's current SDK version yet. To develop GUI using provided API, you can only use Java. Please visit Android Developers web site for more detail. But, you still have to download and set up the SDK because it contains Android Emulator to run compiled binary file.

Thirdly, both Android Source Code and Android SDK are not meant for PowerPC processor. They are meant only for Intel/x86 processor.

Let's start!

Setting Up Your Mac, Installing Repository, and Building the Code

Please visit Get Source web site and follow the step-by-step guidance.

The little tiny problem I have described before is that default Python from Mac has no module named readline. According to the guidance at "Troubleshooting" sub section, you have to install another Python version. What I did, I just removed the line that importing readline. So far, it works fine.

Setting Up Android Emulator

Android Emulator can be found as part of Android SDK. You can get Android SDK from Android Developers web site. Download the Mac OS X (intel) version and follow the installation procedure. It won't be described here. I did it without any problem.

Preparing the Test Code

Get two following Test Code files helloandroid.cpp and Android.mk and put them inside (android_dir)/external/helloandroid/. If the directory is not exist, just create it. (android_dir) is a directory contains Android Source Code. Mine is at /Volumes/android/androidMaster/. On my Mac it will be as follow:

Eka-Kurniawan:helloandroid ekakurniawan$ pwd
/Volumes/android/androidMaster/external/helloandroid

Eka-Kurniawan:helloandroid ekakurniawan$ ls
Android.mk              helloandroid.cpp

Eka-Kurniawan:helloandroid ekakurniawan$

Test Code Location

Following is the source code of Test Code.

#include <stdio.h>

int main(int argc, char** argv)
{
    printf("hello android c++\n");
    if (argc > 1) {
        printf(" - your first input is %s\n", argv[1]);
    }
    return 0;
}

helloandroid.cpp

Following is the Test Code makefile.

ifeq ($(TARGET_ARCH), arm)

LOCAL_PATH := $(call my-dir)

include $(CLEAR_VARS)

LOCAL_SRC_FILES := helloandroid.cpp
LOCAL_MODULE := helloandroid

LOCAL_STATIC_LIBRARIES := libc

include $(BUILD_EXECUTABLE)

endif

Android.mk

Building Test Code

Go to (android_dir) and execute make command. On my Mac, the log of compilation process is as follow:

Eka-Kurniawan:androidMaster ekakurniawan$ pwd
/Volumes/android/androidMaster

Eka-Kurniawan:androidMaster ekakurniawan$ ls
Makefile        build           external        kernel          prebuilt
bionic          dalvik          frameworks      out             system
bootable        development     hardware        packages

Eka-Kurniawan:androidMaster ekakurniawan$ make
build/core/product_config.mk:261: WARNING: adding test OTA key
============================================
TARGET_PRODUCT=generic
TARGET_BUILD_VARIANT=eng
TARGET_SIMULATOR=
TARGET_BUILD_TYPE=release
TARGET_ARCH=arm
HOST_ARCH=x86
HOST_OS=darwin
HOST_BUILD_TYPE=release
BUILD_ID=
============================================
build/core/copy_headers.mk:15: warning: overriding commands for target `out/target/product/generic/obj/include/libpv/getactualaacconfig.h'
build/core/copy_headers.mk:15: warning: ignoring old commands for target `out/target/product/generic/obj/include/libpv/getactualaacconfig.h'
target thumb C++: helloandroid <= external/helloandroid/helloandroid.cpp
target Executable: helloandroid (out/target/product/generic/obj/EXECUTABLES/helloandroid_intermediates/LINKED/helloandroid)
target Non-prelinked: helloandroid (out/target/product/generic/symbols/system/bin/helloandroid)
target Strip: helloandroid (out/target/product/generic/obj/EXECUTABLES/helloandroid_intermediates/helloandroid)
Install: out/target/product/generic/system/app/Mms.apk
Install: out/target/product/generic/system/bin/helloandroid
Finding NOTICE files: out/target/product/generic/obj/NOTICE_FILES/hash-timestamp
Combining NOTICE files: out/target/product/generic/obj/NOTICE.html
gzip -c out/target/product/generic/obj/NOTICE.html > out/target/product/generic/obj/NOTICE.html.gz
Target system fs image: out/target/product/generic/obj/PACKAGING/systemimage_unopt_intermediates/system.img
Install system fs image: out/target/product/generic/system.img
Installed file list: out/target/product/generic/installed-files.txt

Eka-Kurniawan:androidMaster ekakurniawan$

Test Code Compilation Process

The executable file will be located at (android_dir)/out/target/product/generic/obj/EXECUTABLES/helloandroid_intermediates/.

Eka-Kurniawan:helloandroid_intermediates ekakurniawan$ pwd
/Volumes/android/androidMaster/out/target/product/generic/obj/EXECUTABLES/helloandroid_intermediates

Eka-Kurniawan:helloandroid_intermediates ekakurniawan$ ls
LINKED          helloandroid    helloandroid.P  helloandroid.o

Eka-Kurniawan:helloandroid_intermediates ekakurniawan$

Executable File Location

Running Test Code using Android Emulator

First of all, you have to run Android Emulator and wait until Emulation Phone poped-up on your screen. We will not use the Emulation Phone, we will just use Mac Terminal. Go to Android SDK Tools directory and execute Android Shell using adb shell command.

Eka-Kurniawan:tools ekakurniawan$ pwd
/Developer/Applications/android-sdk-mac_x86-1.5_r1/tools

Eka-Kurniawan:tools ekakurniawan$ ls
Jet             android         draw9patch      lib             testhelloworld
NOTICE.txt      apkbuilder      emulator        mksdcard        traceview
adb             ddms            hierarchyviewer sdcard.img
add-accounts.py dmtracedump     hprof-conv      sqlite3

Eka-Kurniawan:tools ekakurniawan$ ./adb shell
#

Android Shell

Please note that we have two consoles now, one is Mac Terminal and the other is Android Shell. Don't be confused.

We will put executable Test Code inside data directory inside Android Shell and execute it form there. Take a look at following files/directories owner, data directory is owned by system. So far, I can't change the files/directories owned by root.

# ls -l
drwxrwxrwt root     root              2009-06-11 15:15 sqlite_stmt_journals
drwxrwx--- system   cache             2009-05-14 15:57 cache
d--------- system   system            2009-06-11 15:15 sdcard
lrwxrwxrwx root     root              2009-06-11 15:15 etc -> /system/etc
drwxr-xr-x root     root              2009-04-22 04:18 system
drwxr-xr-x root     root              1970-01-01 00:00 sys
drwxr-x--- root     root              1970-01-01 00:00 sbin
dr-xr-xr-x root     root              1970-01-01 00:00 proc
-rwxr-x--- root     root         9075 1970-01-01 00:00 init.rc
-rwxr-x--- root     root         1677 1970-01-01 00:00 init.goldfish.rc
-rwxr-x--- root     root       106568 1970-01-01 00:00 init
-rw-r--r-- root     root          118 1970-01-01 00:00 default.prop
drwxrwx--x system   system            2009-05-14 15:57 data
drwx------ root     root              1970-01-01 00:00 root
drwxr-xr-x root     root              2009-06-11 15:15 dev

#

Files and Directories Owner

Copy external file (executable Test Code) into Android Shell data directory using adb push command from Mac Terminal.

Eka-Kurniawan:tools ekakurniawan$ ./adb push /Volumes/android/androidMaster/out/target/product/generic/obj/EXECUTABLES/helloandroid_intermediates/helloandroid /data
152 KB/s (5292 bytes in 0.033s)

Eka-Kurniawan:tools ekakurniawan$

Copying File into Android Shell

If I copy external file into directory own by root, I will get "Read-only file system" error message as follow.

Eka-Kurniawan:tools ekakurniawan$ ./adb push /Volumes/android/androidMaster/out/target/product/generic/obj/EXECUTABLES/helloandroid_intermediates/helloandroid /system/etc
failed to copy '/Volumes/android/androidMaster/out/target/product/generic/obj/EXECUTABLES/helloandroid_intermediates/helloandroid' to '/system/etc/helloandroid': Read-only file system

Eka-Kurniawan:tools ekakurniawan$

"Read-only file system" Error Message

Finally, go back to Android Shell and execute the Test Code as follow.

Eka-Kurniawan:tools ekakurniawan$ ./adb shell
# cd /data

# ls -l
drwxrwx--t system   misc              2009-05-14 15:57 misc
drwxrwx--x shell    shell             2009-05-14 15:57 local
drwxrwx--x system   system            2009-05-14 15:57 data
drwxrwx--x system   system            2009-05-14 15:57 app-private
drwxrwx--x system   system            2009-05-14 15:57 app
drwx------ root     root              2009-05-14 15:57 property
drwxrwxrwx system   system            2009-05-14 15:58 anr
drwxrwx--x system   system            2009-05-14 15:57 dalvik-cache
drwxrwxr-x system   system            2009-05-14 15:58 system
-rwxrwxrwx root     root         5292 2009-06-11 15:00 helloandroid
drwxrwx--- root     root              2009-05-14 15:57 lost+found

# ./helloandroid
hello android c++

# ./helloandroid 1234
hello android c++
 - your first input is 1234

# ./helloandroid asdf
hello android c++
 - your first input is asdf

# exit
Eka-Kurniawan:tools ekakurniawan$

Executing Process and the Output

Following picture was captured after all of the processes.

Captured Screen after All of the Processes

algorithm

2008-05-22T18:53:00.002+08:00

some quotes from algorithm class at mit.

you wanna be a good programmer?
you just program every day for two years, you will be an excellent programmer.

you wanna be a world class programmer?
you can program every day for ten years or,
you can program every day for two years and take an algorithm class.

-- charles e. leiserson

we have both balance our mathematical understanding with our engineering common sense.

-- charles e. leiserson

it's not a common algorithm class, at least for me! i did not even learn about asymptotic notation when i was getting my algorithm and programming class.

octave: speed optimization - fix matrix looping (080426)

2008-04-26T14:31:00.002+08:00

with or without following commands on following octave codes will effect obviously different execution time. from with/without preallocated memory, changing looping sequence, vectorizing, until using specific function will produced different execution time. i have eight cases to be compared, they are:

case 1: without preallocated memory

for i = 1:N
    m1(i, 1:P) = i * ones(1, P);
endfor

elapsed time is 39.3089 seconds.

case 2: preallocated memory with 'm = [];'

m2 = [];
for i = 1:N
    m2(i, 1:P) = i * ones(1, P);
endfor

elapsed time is 38.7618 seconds.

case 3: preallocated memory with 'm(N, P) = 1;'

m3(N, P) = 1;
for i = 1:N
    m3(i, 1:P) = i * ones(1, P);
endfor

elapsed time is 0.126078 second.

case 4: preallocated memory with 'm = ones(N, P);'

m4 = ones(N, P);
for i = 1:N
    m4(i, 1:P) = i * ones (1, P);
endfor

elapsed time is 0.082219 second.

case 5: changing the looping sequence from 'for i = 1:N' to 'for i = N:-1:1'

thanks to ben abbott for his answer to my question related to this optimization. he also suggest me to compare with following code:

m5 = [];
for i = N:-1:1
    m5(i, 1:P) = i * ones (1, P);
endfor

elapsed time is 0.130076 second.

thanks to przemek klosowski for following new cases (case 6 to 8) and idea to add the conclusion.

case 6: nested or more looping with preallocated memory

m6 = ones(N, P);
for i = N:-1:1
    for j = P:-1:1
        m6(i, j) = i;
    endfor
endfor

elapsed time is 15.0053 seconds.

case 7: vectorizing using looping

m7 = ones(N, P);
for j = 1:P
    m7(:,j) = 1:N;
endfor

elapsed time is 0.053149 second.

case 8: vectorizing using 'repmat' function

m8 = repmat((1:N)', 1, P);

elapsed time is 0.045707 second.

conclusion

from case 1-4: one way to speed up looping execution is with preallocated memory.
from case 5: another way to speed up looping execution is with changing the looping sequence.
from case 6: looping is very time consuming. so, avoid of using looping with other commands. this can be different from case to case.
from case 7: another way to speed up looping execution is with vectorizing. vectorizing can be faster than preallocated memory or changing the looping sequence.
from case 8: another way to speed up looping execution is using specific function. using specific function can be faster than vectorizing, preallocated memory, or changing the looping sequence.

overall test code

# Copyright (C) 2008 by lain.ux
# l411v.ux@gmail.com
# www.l411v.com
#
# This program is free software; you can redistribute it and/or modify 
# it under the terms of the GNU General Public License as published by 
# the Free Software Foundation; version 2 of the License.
#
# This program is distributed in the hope that it will be useful, 
# but WITHOUT ANY WARRANTY; without even the implied warranty of 
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License 
# along with this program; if not, write to the 
# Free Software Foundation, Inc., 
# 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

# ------------------------------------------------[ define matrix size ]--
N = 900;
P = 1800;
printf("matrix size: m(%d,%d)\n", N, P);

# -------------------------------------------[ display result function ]--
function display_result(m, N, P)
printf("result:\n", N, P);

# checking first column (expected: 1, 1, 1, ..., 1)
printf("m[1,1] = %d\t", m(1,1));
printf("m[1,2] = %d\t", m(1,2));
printf("m[1,3] = %d\t", m(1,3));
printf("m[1,%d] = %d\n", P, m(1,P));

# checking second column (expected: 2, 2, 2, ..., 2)
printf("m[2,1] = %d\t", m(2,1));
printf("m[2,2] = %d\t", m(2,2));
printf("m[2,3] = %d\t", m(2,3));
printf("m[2,%d] = %d\n", P, m(2,P));

# checking Nth column (expected: 900, 900, 900, ..., 900)
printf("m[%d,1] = %d\t", N, m(N,1));
printf("m[%d,2] = %d\t", N, m(N,2));
printf("m[%d,3] = %d\t", N, m(N,3));
printf("m[%d,%d] = %d\n", N, P, m(N,P));
end

# each column of matrix is the sequence 1, 2, ..., N
# ------------------------------------------------------------[ case 1 ]--
printf("\ncase 1: without preallocated memory\n");
tic
for i = 1:N
    m1(i, 1:P) = i * ones(1, P);
endfor
toc
display_result(m1, N, P);

# ------------------------------------------------------------[ case 2 ]--
printf("\ncase 2: preallocated memory with 'm = [];'\n");
tic
m2 = [];
for i = 1:N
    m2(i, 1:P) = i * ones(1, P);
endfor
toc
display_result(m2, N, P);

# ------------------------------------------------------------[ case 3 ]--
printf("\ncase 3: preallocated memory with 'm(N, P) = 1;'\n");
tic
m3(N, P) = 1;
for i = 1:N
    m3(i, 1:P) = i * ones(1, P);
endfor
toc
display_result(m3, N, P);

# ------------------------------------------------------------[ case 4 ]--
printf("\ncase 4: preallocated memory with 'm = ones(N, P);'\n");
tic
m4 = ones(N, P);
for i = 1:N
    m4(i, 1:P) = i * ones (1, P);
endfor
toc
display_result(m4, N, P);

# ------------------------------------------------------------[ case 5 ]--
printf("\ncase 5: changing the looping sequence ");
printf("from 'for i = 1:N' to 'for i = N:-1:1'\n");
tic
m5 = [];
for i = N:-1:1
    m5(i, 1:P) = i * ones (1, P);
endfor
toc
display_result(m5, N, P);

# ------------------------------------------------------------[ case 6 ]--
printf("\ncase 6: nested or more looping with preallocated memory\n");
tic
m6 = ones(N, P);
for i = N:-1:1
    for j = P:-1:1
        m6(i, j) = i;
    endfor
endfor
toc
display_result(m6, N, P);

# ------------------------------------------------------------[ case 7 ]--
printf("\ncase 7: vectorizing using looping\n");
tic
m7 = ones(N, P);
for j = 1:P
    m7(:,j) = 1:N;
endfor
toc
display_result(m7, N, P);

# ------------------------------------------------------------[ case 8 ]--
printf("\ncase 8: vectorizing using 'repmat' function\n");
tic
m8 = repmat((1:N)', 1, P);
toc
display_result(m8, N, P);

execution result

$ octave-3.0.1 -q trick_080426.octave
matrix size: m(900,1800)

case 1: without preallocated memory
Elapsed time is 39.3089 seconds.
result:
m[1,1] = 1      m[1,2] = 1      m[1,3] = 1      m[1,1800] = 1
m[2,1] = 2      m[2,2] = 2      m[2,3] = 2      m[2,1800] = 2
m[900,1] = 900  m[900,2] = 900  m[900,3] = 900  m[900,1800] = 900

case 2: preallocated memory with 'm = [];'
Elapsed time is 38.7618 seconds.
result:
m[1,1] = 1      m[1,2] = 1      m[1,3] = 1      m[1,1800] = 1
m[2,1] = 2      m[2,2] = 2      m[2,3] = 2      m[2,1800] = 2
m[900,1] = 900  m[900,2] = 900  m[900,3] = 900  m[900,1800] = 900

case 3: preallocated memory with 'm(N, P) = 1;'
Elapsed time is 0.126078 seconds.
result:
m[1,1] = 1      m[1,2] = 1      m[1,3] = 1      m[1,1800] = 1
m[2,1] = 2      m[2,2] = 2      m[2,3] = 2      m[2,1800] = 2
m[900,1] = 900  m[900,2] = 900  m[900,3] = 900  m[900,1800] = 900

case 4: preallocated memory with 'm = ones(N, P);'
Elapsed time is 0.082219 seconds.
result:
m[1,1] = 1      m[1,2] = 1      m[1,3] = 1      m[1,1800] = 1
m[2,1] = 2      m[2,2] = 2      m[2,3] = 2      m[2,1800] = 2
m[900,1] = 900  m[900,2] = 900  m[900,3] = 900  m[900,1800] = 900

case 5: changing the looping sequence from 'for i = 1:N' to 'for i = N:-1:1'
Elapsed time is 0.130076 seconds.
result:
m[1,1] = 1      m[1,2] = 1      m[1,3] = 1      m[1,1800] = 1
m[2,1] = 2      m[2,2] = 2      m[2,3] = 2      m[2,1800] = 2
m[900,1] = 900  m[900,2] = 900  m[900,3] = 900  m[900,1800] = 900

case 6: nested or more looping with preallocated memory
Elapsed time is 15.0053 seconds.
result:
m[1,1] = 1      m[1,2] = 1      m[1,3] = 1      m[1,1800] = 1
m[2,1] = 2      m[2,2] = 2      m[2,3] = 2      m[2,1800] = 2
m[900,1] = 900  m[900,2] = 900  m[900,3] = 900  m[900,1800] = 900

case 7: vectorizing using looping
Elapsed time is 0.053149 seconds.
result:
m[1,1] = 1      m[1,2] = 1      m[1,3] = 1      m[1,1800] = 1
m[2,1] = 2      m[2,2] = 2      m[2,3] = 2      m[2,1800] = 2
m[900,1] = 900  m[900,2] = 900  m[900,3] = 900  m[900,1800] = 900

case 8: vectorizing using 'repmat' function
Elapsed time is 0.045707 seconds.
result:
m[1,1] = 1      m[1,2] = 1      m[1,3] = 1      m[1,1800] = 1
m[2,1] = 2      m[2,2] = 2      m[2,3] = 2      m[2,1800] = 2
m[900,1] = 900  m[900,2] = 900  m[900,3] = 900  m[900,1800] = 900

openmp c/c++ on intel and linux using sun compiler

2008-04-18T09:52:00.003+08:00

i have written another openmp topic titled openmp c/c++ on intel and linux using intel compiler. this blog is about how to do it again using sun compiler. following is the steps:

setting sunstudio

sunstudio is a development packet from sun microsystems. it contains netbeans ide and sun c compiler. we will need both of them to create the project and compile the code.

getting source code

i use a same source code as i use it on intel compiler. please find the source code from another blog titled openmp c/c++ on intel and linux using intel compiler on sample code bulleted list.

compiling source code

after setting up the project and loading the source code in, follow following steps to activate openmp feature during compilation process.

open project properties window: on project window, right click on project name, and select properties.
activate openmp feature: on categories tree box, select configuration properties - c/c++/fortran - c compiler - general. on properties table box, change multithreading level form none to openmp. click on ok button.
build the project: on menu bar, click on build - build main project.

activate openmp compilation feature

executing the binary file

you need to set maximum stack size with following command. i still don't know how to run the following command on the sunstudio ide before i execute the binary file. so i execute the binary file on console.

$ ulimit -s unlimited

you need also to set number of thread to use. i use intel core 2 duo processor. it's dual processor so i set it with 2.

$ export OMP_NUM_THREADS=2
$ export OMP_DYNAMIC=FALSE

i name the binary file with openmp feature, with sun_openmp. following is the execution result.

$ ./sun_openmp
Using time() for wall clock time
Problem size: c(600,2400) = a(600,1200) * b(1200,2400)
Calculating product 5 time(s)

We are using 2 thread(s)

Finished calculations.
Matmul kernel wall clock time = 6.00 sec
Wall clock time/thread = 3.00 sec
MFlops = 2880.000000

i name the binary file without openmp feature, with sun_not_openmp. following is the execution result.

$ ./sun_not_openmp
Using time() for wall clock time
Problem size: c(600,2400) = a(600,1200) * b(1200,2400)
Calculating product 5 time(s)

We are using 1 thread(s)

Finished calculations.
Matmul kernel wall clock time = 17.00 sec
Wall clock time/thread = 17.00 sec
MFlops = 1016.470588

system monitor

following captured kde system guard (performance monitor) shows cpu load of cpu0 and cpu1. both numbers on purple color describe:
(1) single processor working: only cpu0 is active 100%, the process is finished slower
(2) dual processors working: both cpu0 and cpu1 are active 100%, the process is finished faster

openmp api user's guide

for more deep understanding, please reefer to sun studio 12: openmp api user's guide.

openmp c/c++ on intel and linux using intel compiler

2008-04-02T23:59:00.004+08:00

i'm using intel core 2 duo processor and debian gnu/linux 4.0. i'm now, in the step of learning openmp and i want to know how fast dual processors can run compared to single processor.

hardware and software specification

following processor information is taken from /proc/cpuinfo file.

vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 CPU          6600  @ 2.40GHz
stepping        : 6
cpu MHz         : 2400.778
cache size      : 4096 KB
physical id     : 0
siblings        : 2
cpu cores       : 2

i'm using debian gnu/linux 4.0.

$ uname -a
Linux l411v 2.6.18-6-686 #1 SMP Sun Feb 10 22:11:31 UTC 2008 i686 GNU/Linux

i get and install intel c++ compiler professional edition for linux for non-commercial use.

$ icc --version
icc (ICC) 10.1 20080112
Copyright (C) 1985-2007 Intel Corporation.  All rights reserved.

setting environment

set executable path to intel c++ compiler binary directory.

$ export PATH=$PATH:/usr/share/intel/cc/10.1.012/bin/

set library path to intel c++ dynamic library directory.

$ export LD_LIBRARY_PATH=/usr/share/intel/cc/10.1.012/lib
$ echo $LD_LIBRARY_PATH
/usr/share/intel/cc/10.1.012/lib

fixing bug

i get openmp sample code (openmp_sample.c) after installing intel c++ compiler from sample directory. please find the sample code below. to activate openmp feature, add additional -openmp compiling parameter. i found some errors when compiling the sample code without -openmp compiling parameter. the errors as follow:

$ icc -std=c99 openmp_sample.c
openmp_sample.c(106): warning #161: unrecognized #pragma
     #pragma omp parallel private(i,j,k)
             ^

openmp_sample.c(109): warning #161: unrecognized #pragma
      #pragma omp single nowait
              ^

openmp_sample.c(119): warning #161: unrecognized #pragma
      #pragma omp for nowait
              ^

openmp_sample.c(126): warning #161: unrecognized #pragma
      #pragma omp for nowait
              ^

what i need to do just adding preprocessor to block all openmp features on the sample code. so change from:

  #pragma omp parallel private(i,j,k)

to:

#ifdef _OPENMP
  #pragma omp parallel private(i,j,k)
#endif

compile and run

ulimit command controls the user resources available to a process started by the shell. you need set the stack size to an appropriate size; otherwise, the application will generate a segmentation fault. following command sets the maximum stack size to unlimited.

$ ulimit -s unlimited

compile with openmp feature and static linking mode:

$ icc -std=c99 -openmp -static openmp_sample.c
openmp_sample.c(119): (col. 5) remark: OpenMP DEFINED LOOP WAS PARALLELIZED.
openmp_sample.c(126): (col. 5) remark: OpenMP DEFINED LOOP WAS PARALLELIZED.
openmp_sample.c(106): (col. 3) remark: OpenMP DEFINED REGION WAS PARALLELIZED.

$ ls -l
total 1092
-rwxr-xr-x 1 lain lain 1105135 2008-04-02 11:48 a.out
-rw-r--r-- 1 lain lain    4702 2008-04-02 11:06 openmp_sample.c

$ ./a.out

Using time() for wall clock time
Problem size: c(600,2400) = a(600,1200) * b(1200,2400)
Calculating product 5 time(s)

We are using 2 thread(s)

Finished calculations.
Matmul kernel wall clock time = 6.00 sec
Wall clock time/thread = 3.00 sec
MFlops = 2880.000000

compile with openmp feature and dynamic linking mode:

$ icc -std=c99 -openmp openmp_sample.c
openmp_sample.c(124): (col. 5) remark: OpenMP DEFINED LOOP WAS PARALLELIZED.
openmp_sample.c(133): (col. 5) remark: OpenMP DEFINED LOOP WAS PARALLELIZED.
openmp_sample.c(107): (col. 3) remark: OpenMP DEFINED REGION WAS PARALLELIZED.

$ ls -l
total 44
-rwxr-xr-x 1 lain lain 34087 2008-04-02 12:01 a.out
-rw-r--r-- 1 lain lain  4702 2008-04-02 11:06 openmp_sample.c

$ ./a.out
Using time() for wall clock time
Problem size: c(600,2400) = a(600,1200) * b(1200,2400)
Calculating product 5 time(s)

We are using 2 thread(s)

Finished calculations.
Matmul kernel wall clock time = 6.00 sec
Wall clock time/thread = 3.00 sec
MFlops = 2880.000000

compile without openmp feature and static linking mode:

$ icc -std=c99 -static openmp_sample.c

$ ls -l
total 512
-rwxr-xr-x 1 lain lain 509458 2008-04-02 11:49 a.out
-rw-r--r-- 1 lain lain   4702 2008-04-02 11:06 openmp_sample.c

$ ./a.out
Using time() for wall clock time
Problem size: c(600,2400) = a(600,1200) * b(1200,2400)
Calculating product 5 time(s)

We are using 1 thread(s)

Finished calculations.
Matmul kernel wall clock time = 17.00 sec
Wall clock time/thread = 17.00 sec
MFlops = 1016.470588

compile without openmp feature and dynamic linking mode:

$ icc -std=c99 openmp_sample.c

$ ls -l
total 32
-rwxr-xr-x 1 lain lain 23570 2008-04-02 12:03 a.out
-rw-r--r-- 1 lain lain  4702 2008-04-02 11:06 openmp_sample.c

$ ./a.out
Using time() for wall clock time
Problem size: c(600,2400) = a(600,1200) * b(1200,2400)
Calculating product 5 time(s)


We are using 1 thread(s)

Finished calculations.
Matmul kernel wall clock time = 17.00 sec
Wall clock time/thread = 17.00 sec
MFlops = 1016.470588

conclusion

| openmp  | number of | linking | file size |  time to  |    mega      |
| feature |  thread   |  mode   |  (byte)   |  finish   |    flops     |
|         |           |         |           | (seconds) |              |
+---------+-----------+---------+-----------+-----------+--------------+
|   yes   |     2     | static  | 1,105,135 |     6     | 2,880.000000 |
|   yes   |     2     | dynamic |    34,087 |     6     | 2,880.000000 |
|   no    |     1     | static  |   509,458 |    17     | 1,016.470588 |
|   no    |     1     | dynamic |    23,570 |    17     | 1,016.470588 |

system monitor

sample code

openmp_sample.c file:

/*
 * Copyright (C) 2006-2007 Intel Corporation. All Rights Reserved.
 *
 * The source code contained or described herein and all
 * documents related to the source code ("Material") are owned by
 * Intel Corporation or its suppliers or licensors. Title to the
 * Material remains with Intel Corporation or its suppliers and
 * licensors. The Material is protected by worldwide copyright
 * laws and treaty provisions.  No part of the Material may be
 * used, copied, reproduced, modified, published, uploaded,
 * posted, transmitted, distributed,  or disclosed in any way
 * except as expressly provided in the license provided with the
 * Materials.  No license under any patent, copyright, trade
 * secret or other intellectual property right is granted to or
 * conferred upon you by disclosure or delivery of the Materials,
 * either expressly, by implication, inducement, estoppel or
 * otherwise, except as expressly provided in the license
 * provided with the Materials.
 *
 * [DESCRIPTION]
 * Each element of the product matrix c[i][j] is 
 * computed from a unique row and
 * column of the factor matrices, a[i][k] and b[k][j].
 *
 * In the multithreaded implementation, each thread can
 * concurrently compute some submatrix of the product without
 * needing OpenMP data or control synchronization.
 *
 * The algorithm uses OpenMP* to parallelize the outer-most loop,
 * using the "i" row index.
 *
 * Both the outer-most "i" loop and middle "k" loop are manually
 * unrolled by 4.  The inner-most "j" loop iterates one-by-one
 * over the columns of the product and factor matrices.
 *
 * [COMPILE]
 * Use the following compiler options to compile both multi- and 
 * single-threaded versions.
 *
 * Parallel compilation:
 *  You must set the stacksize to an appropriate size; otherwise,
 *  the application will generate a segmentation fault. 
 *  Linux* and Mac OS* X: appropriate ulimit commands are shown for 
 *  bash shell.
 *
 *  Windows*: /Qstd=c99 /Qopenmp /F256000000
 *
 *  Linux*:   ulimit -s unlimited
 *            -std=c99 -openmp
 * 
 *  Mac OS* X:  ulimit -s 64000
 *            -std=c99 -openmp
 *
 * Serial compilation:
 *
 *  Use the same command, but omit the -openmp (Linux and Mac OS X)
 *  or /Qopenmp (Windows) option.
 *
 */

#include <stdio.h>
#include <time.h>
#include <float.h>
#include <math.h>
#ifdef _OPENMP
#include <omp.h>
#endif
#define bool _Bool
#define true 1
#define false 0

// Matrix size constants
// Be careful to set your shell's stacksize limit to a high value if you
// wish to increase the SIZE.
#define SIZE     4800     // Must be a multiple of 8.
#define M        SIZE/8
#define N        SIZE/4
#define P        SIZE/2
#define NTIMES   5        // product matrix calculations

int main(void)
{
  double a[M][N], b[N][P], c[M][P], walltime;
  bool nthr_checked=false;
  time_t start;

  int i, j, k, l, i1, i2, i3, k1, k2, k3, nthr=1;

  printf("Using time() for wall clock time\n");
  printf("Problem size: c(%d,%d) = a(%d,%d) * b(%d,%d)\n",
         M, P, M, N, N, P);
  printf("Calculating product %d time(s)\n", NTIMES);

  // a is identity matrix
  for (i=0; i<M; i++)
    for (j=0; j<N; j++)
      a[i][j] = 1.0;

  // each column of b is the sequence 1,2,...,N
  for (i=0; i<N; i++)
    for (j=0; j<P; j++)
      b[i][j] = i+1.;

  start = time(NULL);

#ifdef _OPENMP
  #pragma omp parallel private(i,j,k)
#endif
  {
  for (l=0; l<NTIMES; l++) {
#ifdef _OPENMP
    #pragma omp single nowait
#endif
    if (!nthr_checked) {
#ifdef _OPENMP
      nthr = omp_get_num_threads();
#endif
      printf( "\nWe are using %d thread(s)\n", nthr);
      nthr_checked = true;
    }

    // Initialize product matrix
#ifdef _OPENMP
    #pragma omp for nowait
#endif
    for (i=0; i<M; i++)
      for (j=0; j<P; j++)
        c[i][j] = 0.0;

    // Parallelize by row.  The threads don't need to synchronize at
    // loop end, so "nowait" can be used.
#ifdef _OPENMP
    #pragma omp for nowait
#endif
    for (i=0; i<M; i++) {
      for (k=0; k<N; k++) {
        // Each element of the product is just the sum 1+2+...+n
        for (j=0; j<P; j++) {
          c[i][j]  += a[i][k]  * b[k][j];
        }
      }
    }
  } // #pragma omp parallel private(i,j,k)
  } // l=0,...NTIMES-1

  walltime = time(NULL) - start;
  printf("\nFinished calculations.\n");
  printf("Matmul kernel wall clock time = %.2f sec\n", walltime);
  printf("Wall clock time/thread = %.2f sec\n", walltime/nthr);
  printf("MFlops = %f\n",
      (double)(NTIMES)*(double)(N*M*2)*(double)(P)/walltime/1.0e6);

  return 0;
}

syntax highlighting on blog

2008-03-29T14:41:00.002+08:00

since syntax highlighter doesn't support vhdl and verilog code yet, so i manually convert the highlighted text file into html file. following the steps:

open your code using kwrite and set the highlighting color as your flavor by selecting "Settings > Configure Editor..." and clicking on "Fonts & Colors"

export your code into html file by clicking on "File > Export as HTML..." and "Save"

copy the html source of your html file by opening your html file with your internet browser and clicking on "View > Page Source" (if you are using mozilla firefox). copy from tag <pre> to </pre>.

paste it into your new posting blog in side "Edit Html" tab box and click back on "Compose" tab box to see the result.

add border to make it beautiful by changing html tag <pre> with following settings.

<pre style="border: 1px dashed rgb(64, 64, 64); margin: 0em; padding: 1em; overflow: auto; background-color: rgb(0, 0, 0);">

done! following examples of highlighted vhdl and verilog code

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;

entity Const_Unit is
   Port (Imm : in std_logic_vector(15 downto 0);
         CS : in std_logic;
         Const : out std_logic_vector(31 downto 0));
end Const_Unit;

architecture Behavioral of Const_Unit is
begin
   -- pass the 16 lsb value.
   Const(15 downto 0) <= Imm(15 downto 0);

   process (CS, Imm) begin
      if (CS = '0') then
         -- unsign value
         Const(31 downto 16) <= X"0000";
      else
         -- sign value (sign extension)
         for i in 31 downto 16 loop
            Const(i) <= Imm(15);
         end loop;
      end if;
   end process;
end Behavioral;

code: highlighted vhdl code

`timescale 1ns / 1ns

`include "../inc/ctr.h"

module ctr(
   // input
   clk, rst,
   // output
   out
);
   // i/os
   input                      clk,        // clock
                              rst;        // reset
   output [`WIDTH-1:0]        out;        // output
   // internal signals
   wire                       clk,        // clock
                              rst;        // reset
   reg    [`WIDTH-1:0]        out;        // output

   always @(posedge clk or posedge rst) begin
      if (rst)
         out <= 0;
      else
         out <= out + 1;
   end

endmodule

code: highlighted verilog code

opensparc for hobby (setting ide)

2007-11-24T22:07:00.007+08:00

the first time i knew and directly downloaded opensparc source code was eight months ago. i grab it just for hobby so i don't have any plan to buy any expensive ide, simulator, synthesizer, or loader. i don't even want to put it into a die. i want to grab it using open source or free software and load it (part of it) into an fpga board.

what did i do so far are:

joining related project

i join opensparc-t1 s1 project and fpga project.

finding open source software

i'm currently using debian gnu/linux 4.0 for the operating system, eclipse 3.3.1.1 and verilog editor 0.5.2 for the ide, icarus verilog 0.8 for the simulator, gtkwave 1.3.81 for the waveform viewer of the simulation result. for the synthesizer, i have tried s1 core using icarus verilog but it fail.

eclipse ide for verilog editor on debian gnu/linux 4.0

i have added opensparct1.1.5 and s1 core as eclipse project. i also set the eclipse to automatically run some external tools for s1 project to build icarus simulation, run icarus simulation, and display test waveform.

in the following example, i extract the s1 core under .../openSparc/s1_core/ directory.

following steps show you how to set the external tools to build icarus simulation:
+ select run - external tools - open external tools dialog...
+ on the left box, double click program
+ on the right box, fill in:
___- name: s1 - build icarus simulation
+ on main tab, fill in:
___- location: .../openSparc/s1_core/tools/bin/build_icarus
_____(location of build_icarus script)
___- working directory: ${workspace_loc:/s1_core}
_____(s1 core working directory)
+ on environment tab:
___- click on new... button
___- fill in variable name with FILELIST_ICARUS, value with .../openSparc/s1_core/hdl/filelist.icarus
_____(location to filelist.icarus file)
___- click on new... button again
___- fill in variable name with S1_ROOT, value with .../openSparc/s1_core
_____(location to filelist.icarus file)
+ please make sure that the directories and environment variables are correct. one mistake can destroy your data. it because the s1 script execute "rm -rf *" command.
+ click on apply and close button
+ the new setting will appear at run - external tools - s1 - build icarus simulation

following steps show you how to set the external tools to run icarus simulation:
+ select run - external tools - open external tools dialog...
+ on the left box, double click on program
+ on the right box, fill in:
___- name: s1 - run icarus simulation
+ on main tab, fill in:
___- location: .../openSparc/s1_core/tools/bin/run_icarus
_____(location to run_icarus script)
___- working directory: ${workspace_loc:/s1_core}
_____(s1 core working directory)
+ on environment tab:
___- click on new... button
___- fill in variable name with S1_ROOT, value with .../openSparc/s1_core
_____(location to filelist.icarus file)
+ click on apply and close button
+ the new setting will appear at run - external tools - s1 - run icarus simulation

following steps show you how to set the external tools to display test waveform:
+ select run - external tools - open external tools dialog...
+ on the left box, double click on program
+ on the right box, fill in:
___- name: s1 - display test waveform
+ on main tab, fill in:
___- location: /usr/bin/gtkwave
_____(location of gtkwave application)
___- working directory: ${workspace_loc:/s1_core}
_____(s1 core working directory)
___- arguments: run/sim/icarus/trace.vcd tools/src/gtkwave.sav
+ on environment tab:
___- click on new... button
___- fill in variable name with S1_ROOT, value with .../openSparc/s1_core
_____(location to filelist.icarus file)
+ click on apply and close button
+ the new setting will appear at run - external tools - s1 - display test waveform

the default font setting form eclipse is too big for me, so i change it from window - preferences... than select general - appearance - colors and fonts. some other gtk default font can be changed also. read this blog on how to make eclipse look good on linux.

finding free software

i have installed xilinx ise webpack 9.2i on my debian gnu/linux 4.0 box. i need only to install a new library and it just work. as the default, debian comes with libstdc++6, but xilinx ise webpack 9.2i requires libstdc++5. just install the old library without removing the new one.

the synthesis works fine but you can't find any fpga board that is supported by xilinx ise webpack edition that can feed opensparc t1or even s1 core in. the default simulator (just a simple simulator) form xilinx ise webpack also can't simulate s1 core test.

xilinx ise webpack on debian gnu/linux 4.0