Cadence.com will be under maintenance from Friday, Oct. 3rd at 6pm (PST) thru Sunday, Oct 5th at 11pm (PST).
Cadence.com login, registration, community posting and commenting functionalities will be disabled.
Home > Community > Blogs > Custom IC Design > skill for the skilled virtuoso applications of skill
 
Login with a Cadence account.
Not a member yet?
Create a permanent login account to make interactions with Cadence more convenient.

Register | Membership benefits
Get email delivery of the Custom IC Design blog (individual posts).
 

Email

* Required Fields

Recipients email * (separate multiple addresses with commas)

Your name *

Your email *

Message *

Contact Us

* Required Fields
First Name *

Last Name *

Email *

Company / Institution *

Comments: *

SKILL for the Skilled: Virtuoso Applications of SKILL++

Comments(3)Filed under: Custom IC Design, Virtuoso, SKILL, Team SKILL, LISP, SKILL++, IC 6.1.5, Virtuoso IC6.1.5, sorting, sort, closures

In this posting, I continue looking at applications of SKILL++. In particular, I'll also discuss how to create functions that hold onto their state. I'll use these functions to implement multiple-criteria (cascading) sort predicates. I'll look at ways to sort layout pins counter-clockwise around the center point of the design.

Quick Review

 In the previous posting we looked at an implementation of genCmpFunction which I'll repeat here.

;; Example 5.11
(defun genCmpFunction (@key (test lessp)
(key identity)) ;; see example 5.10
(lambda (A B)
(test (key A)
(key B))))

The value passed as ?key is a function, which given the sort candidate, retrieves the value to be compared. Thus if we wish to sort a list of db-instances by name, we need to pass as ?key a function that given a db-instance will return its name. In example 5.15, we did just that; we passed ?key 'name (lambda (i) i->name).

The getter function

This idiom is actually common enough that we can introducing a new SKILL++ function, named getter, which generates a read-accessor to access a given property name.

;; Example 5.16
(defun getter (propertyName)
(lambda (object)
(get object propertyName)))
The function getter takes a property name as its argument and returns a newly generated unary function which will retrieve the value of that property name from its argument. For example given the symbol name, it will return turn a unary function which will retrieve the value of the property name. (funcall (getter 'name) db_inst) is the same as db_inst->name. Of course this is not very interesting used by itself, but is useful in conjunction with other functions like genCmpFunction and genCascadeCmpFunction which will be seen later.

Example 5.17 shows the code example 5.15 but using the getter function rather than lambda.

;; Example 5.17
(sort (geGetEditCellView)->instances
(genCmpFunction ?test alphalessp
?key (getter 'name)))
What's a closure?

Functions such as genCmpFunction from example 5.11, and getter from example 5.17 are subtly different than functions available in traditional SKILL++. Notice that genCmpFunction returns an on-the-fly function created by (lambda ...). The code within the lambda found in genCmpFunction references two free variables, test and key. These free variables are not declared by or inside the lambda. Likewise, in the function getter, the lambda expression references but does not define propertyName. Functions which extend the life-time of variables defined elsewhere and hold on to these closed-over variables in this way are referred to as closures. In example 5.17, the sort function is called only after genCmpFunction returns. Nevertheless, the closure returned from genCmpFunction holds onto the local variables of genCmpFunction, namely test and key.

Many other Lisp dialects as well as some other programming languages (such as ML, SmallTalk, and JavaScript) implement and support closures. You can find out more about closures on wikipedia.

Sorting pins in a layout cellView

Example 5.18 shows a function which sorts the pin figures in a given layout cellView into counter-clockwise order around the center of the cellView.

;; Example 5.18
(defun sortPinFigs (cv)
(let ((cv_center (centerBox cv->bBox))
(cv_pin_figs (foreach mapcan term cv->terminals
(foreach mapcan pin term->pins
pin->figs))))
(sort cv_pin_figs
(genCmpFunction
?key (lambda (fig)
(let ((fig_center (centerBox fig->bBox)))
(atan2 (yCoord cv_center) - (yCoord fig_center)
(xCoord cv_center) - (xCoord fig_center))))))))
Note that the function sortPinFigs in example 5.18 assumes there is no pin whose center is in the cellView center, because in that case atan2 would fail.

Cascading sort

Another limitation of sortPinFigs as implemented in example 5.18 is that two different pin figures might be at the same angle. It would be great if the sortPinFigs function would sort pins deterministically. We need a secondary sort criteria. For example, if two figures appear at the same angle, then sort by their distance from the center. But there might actually be some overlapping pins which have the same center, in which case a third criteria is needed, such as sort by layer name (or terminal name, or pin name, or left edge).

In general, whenever sorting objects based not on their identity but on some attribute, it might happen that two different objects share a value of that attribute. As in the example above, when sorting file names according to file sizes, it might of course happen that two different files have the same size. Example 5.19 shows a function genCascadeCmpFunction which is more general than genCmpFunction. The genCascadeCmpFunction function generates a compare predicate based on a sequence of cascading key/test pairs.

;; Example 5.19
(defun genCascadeCmpFunction (key lessp @rest others)
(lambda (a b)
(labels ((cascade (key lessp others "UUl")
(cond
((lessp (key a) (key b)))
((lessp (key b) (key a))
nil)
(others
(cascade (car others) (cadr others) (cddr others))))))
(cascade key lessp others))))

 

Sorting strings by cascading criteria

To sort a list of strings proceed first by string-length, then (if they have the same string-length) alphabetically.

;; Example 5.20
(sort (list "c" "abc" "jkl" "b" "hello" "d" "world" "xyz")
(genCascadeCmpFunction strlen lessp
identity alphalessp))

===> ("b" "c" "d" "abc" "jkl" "xyz" "hello" "world")
Sorting file names by cascading criteria

To sort a list of file names first by file length, then alphabetically according to name, you can use the following.

;; Example 5.21
(sort (getDirFiles ".")
(genCascadeCmpFunction fileLength lessp
identity alphalessp))

Sorting db-shapes by cascading criteria

To sort a list of db-shapes, first according to their layer name, then layer-purpose, then left-to-right by left edge, then right-to-left right edge, then top-to-bottom top edge, then bottom-to-top bottom edge, use the following.

;; Example 5.22
(sort list_of_shapes
(genCascadeCmpFunction (lambda (obj) obj->layerName) alphalessp
(lambda (obj) obj->purpose) alphalessp
leftEdge lessp
rightEdge greaterp
topEdge greaterp
bottomEdge lessp))
We can rewrite the call above to something simpler using the getter function defined in example 5.16.
;; Example 5.23
(sort list_of_shapes
(genCascadeCmpFunction (getter 'layerName) alphalessp
(getter 'purpose) alphalessp
leftEdge lessp
rightEdge greaterp
topEdge greaterp
bottomEdge lessp))
Summary

The examples shown above illustrate a interesting and powerful feature of SKILL++, closures. You might also find some of the examples useful to simply copy and paste into your programs. Remember to use the .ils extension.

See alsoJim Newton

Comments(3)

By Team SKILL on June 8, 2011
More examples of how to use sort and genCascadeCmpFunction might be helpful.

If you want to sort a list of 3-d points, first by the x-coord, next by the y-coord, and finally by the z-coord, you can use the following.

(sort '((1 2 3)
         (3 2 1)
         (2 1 3)
         (1 1 2)
         (4 1 2)
         (1 1 1)
         (1 2 4)
         (4 2 2)
         (2 1 1)
         (1 1 3)
         (4 1 1)
         (1 2 1)
         (3 1 2))
         (genCascadeCmpFunction car lessp
                      cadr lessp
                      caddr lessp))

This expression returns the following list of ordered points:
((1 1 1)
 (1 1 2)
 (1 1 3)
 (1 2 1)
 (1 2 3)
 (1 2 4)
 (2 1 1)
 (2 1 3)
 (3 1 2)
 (3 2 1)
 (4 1 1)
 (4 1 2)
 (4 2 2))

By Team SKILL on June 8, 2011
Another example:

If you want to sort a list of DPLs, first according to the ->x field,
then the ->y field, and finally the ->z field, you can use something like the following:

(sort '((nil x 1.1 y 1.3 z 1.2)
         (nil x 2.1 y 1.3 z 1.3)
         (nil x 3.1 y 1.2 z 1.3)
         (nil x 4.1 y 1.2 z 1.3)
         (nil x 2.1 y 1.3 z 1.4)
         (nil x 4.1 y 1.3 z 1.3)
         (nil x 2.1 y 1.2 z 1.3)
         (nil x 3.1 y 1.3 z 1.4)
         (nil x 1.1 y 1.3 z 1.3)
         (nil x 3.1 y 1.3 z 1.3)
         (nil x 1.1 y 1.2 z 1.3)
         (nil x 4.1 y 1.3 z 1.4))
         (genCascadeCmpFunction (getter 'x) lessp
                                                    (getter 'y) lessp
                                                    (getter 'z) lessp))

This expression evaluates to the following list.

((nil x 1.1 y 1.2 z 1.3)
 (nil x 1.1 y 1.3 z 1.2)
 (nil x 1.1 y 1.3 z 1.3)
 (nil x 2.1 y 1.2 z 1.3)
 (nil x 2.1 y 1.3 z 1.3)
 (nil x 2.1 y 1.3 z 1.4)
 (nil x 3.1 y 1.2 z 1.3)
 (nil x 3.1 y 1.3 z 1.3)
 (nil x 3.1 y 1.3 z 1.4)
 (nil x 4.1 y 1.2 z 1.3)
 (nil x 4.1 y 1.3 z 1.3)
 (nil x 4.1 y 1.3 z 1.4))

By Team SKILL on June 8, 2011
If you want to sort a list like the one below, with the following priorities:

1.  the name in the second position ("bill" "fred" "george" "jane") in alphabetical order,
2.  the ->y field of the dpl in the 3rd position in increasing order,
3.  the ->x field of the dpl in the 3rd position in increasing order,
4.  the element in the first position in increasing order

(sort `((10 "fred" (nil x 1.1 y 1.2))
          (11 "george" (nil x 1.1 y 1.2))
        (11 "jane" (nil x 1.1 y 1.2))
        (14 "jane" (nil x 1.1 y 1.2))
        (10 "fred" (nil x 1.3 y 1.2))
        (14 "fred" (nil x 1.2 y 1.2))
        (13 "fred" (nil x 1.3 y 1.2))
        (11 "jane" (nil x 1.2 y 1.2))
        (10 "bill" (nil x 1.1 y 1.22))
        (14 "jane" (nil x 1.2 y 1.4))
        (10 "bill" (nil x 1.1 y 1.24))
        (10 "fred" (nil x 1.2 y 1.2))
        (10 "bill" (nil x 1.1 y 1.23))
        (11 "jane" (nil x 1.2 y 1.21))
        (12 "fred" (nil x 1.2 y 1.2))
        (13 "fred" (nil x 1.2 y 1.2))
        (14 "jane" (nil x 1.2 y 1.22))
        (10 "fred" (nil x 1.1 y 1.23))
        (10 "bill" (nil x 1.1 y 1.2))
        (10 "george" (nil x 1.1 y 1.2)))
        (genCascadeCmpFunction cadr alphalessp
                        (lambda (obj) (nth 2 obj)->y) lessp
                        (lambda (obj) (nth 2 obj)->x) lessp
                        car lessp))

This evaluates to the following list:

((10 "bill"   (nil x 1.1 y 1.2))
 (10 "bill"  (nil x 1.1 y 1.22))
 (10 "bill"  (nil x 1.1 y 1.23))
 (10 "bill"  (nil x 1.1 y 1.24))
 (10 "fred"  (nil x 1.1 y 1.2))
 (10 "fred"  (nil x 1.2 y 1.2))
 (12 "fred"  (nil x 1.2 y 1.2))
 (13 "fred"  (nil x 1.2 y 1.2))
 (14 "fred"  (nil x 1.2 y 1.2))
 (10 "fred"  (nil x 1.3 y 1.2))
 (13 "fred"  (nil x 1.3 y 1.2))
 (10 "fred"  (nil x 1.1 y 1.23))
 (10 "george" (nil x 1.1 y 1.2))
 (11 "george" (nil x 1.1 y 1.2))
 (11 "jane"  (nil x 1.1 y 1.2))
 (14 "jane"  (nil x 1.1 y 1.2))
 (11 "jane"  (nil x 1.2 y 1.2))
 (11 "jane"  (nil x 1.2 y 1.21))
 (14 "jane"  (nil x 1.2 y 1.22))
 (14 "jane"  (nil x 1.2 y 1.4)))

Leave a Comment


Name
E-mail (will not be published)
Comment
 I have read and agree to the Terms of use and Community Guidelines.
Community Guidelines
The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.